Re: 35s/42S mini challenge, my solution and part 2 Message #13 Posted by Egan Ford on 21 Sept 2007, 3:47 p.m., in response to message #1 by Egan Ford
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 2^{j}2^{k} 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 playbyplay to explain how this works.
Consider the expression 2^{25}2^{17} = 33423360.
^{ } 2^{25} = 00000010000000000000000000000000 = 33554432
^{ } 2^{17} = 00000000000000100000000000000000 = 131072
2^{25}  2^{17} = 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^{j1}.
Let x = 2^{25}2^{17},
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 2^{j} or 2^{k}. Obviously if you can identify one you can find the other and then use log_{2} to get j and k. I have a 3 step solution for 2^{k} that is identical on the 35s/42S/16C.
