Thank you all for participating in this mini challenge. I selected this challenge because there was more than one way to do it. The most economical way was to use the bitwise operators in the LOGIC menu of the 35s/42S. (I left a hint to consider using logic.)
Paul Dale did come up with a logical 9 step solution. Congratulations Paul!
Part 1 Problem
Write in 9 steps or less of logic (LBL/RTN not counted) a program that can identify if a positive integer can be represented as 2j-2k where j>=k>=0. If so return a 0, if not return > 0. There is no need to identify j and k.
Part 1 Solution
My solution is similar to Paul's and will work unmodified on the 35s, 42S, 16C, and possibility other models with bitwise operators. I have been unable to get it down to less than 9 steps.
ENTER
ENTER
ENTER
1
-
OR
1
+
AND
Below is a play-by-play to explain how this works.
Consider the expression 225-217 = 33423360.
225 = 00000010000000000000000000000000 = 33554432
217 = 00000000000000100000000000000000 = 131072
225 - 217 = 00000001111111100000000000000000 = 33423360
As Paul pointed out it this problem is about identifying an single contiguous block of 1s. 2
j - 2
k will always be a single block of bits with the range 2
k to 2
j-1.
Let x = 225-217,
First subtract 1 from x then OR it with x. This replaces all right trailing zeros with 1s:
x = 00000001111111100000000000000000 = 33423360
x - 1 = 00000001111111011111111111111111 = 33423359
(x - 1) | x = 00000001111111111111111111111111 = 33554431
Next add 1 to create a 2
n number > x:
((x - 1) | x) + 1 = 00000010000000000000000000000000 = 33554432
Lastly AND that number with x to get 0:
((x - 1) | x) + 1 = 00000010000000000000000000000000 = 33554432
x = 00000001111111100000000000000000 = 33423360
(((x - 1) | x) + 1) & x = 00000000000000000000000000000000 = 0
Any other number without a single contigous block of 1s will fail, e.g.:
x = 00000000101111000110000101001110 = 12345678
x - 1 = 00000000101111000110000101001101 = 12345677
(x - 1) | x = 00000000101111000110000101001111 = 12345679
The last operation did replace all the right trailing zeros with 1s (all one of them), but when adding 1 a 2
n number > x is not obtained:
((x - 1) | x) + 1 = 00000000101111000110000101010000 = 12345680
ANDing it with x does not yield 0:
((x - 1) | x) + 1 = 00000000101111000110000101010000 = 12345680
x = 00000000101111000110000101001110 = 12345678
(((x - 1) | x) + 1) & x = 00000000101111000110000101000000 = 12345664
Part 2 Problem
In as few steps as possible identify 2j or 2k. Obviously if you can identify one you can find the other and then use log2 to get j and k. I have a 3 step solution for 2k that is identical on the 35s/42S/16C.