We can assume an int is 32 bits in 2's compliment The only Legal operators are: ! ~ & ^ | + << >>
At this point i am using brute force
int a=0x01;
x=(x+1)>>1; //(have tried with just x instead of x+1 as well)
a = a+(!(!x));
... with the last 2 statements repeated 32 times. This adds 1 to a everytime x is shifted one place and != 0 for all 32 bits
Using the test compiler it says my method fails on test case 0x7FFFFFFF (a 0 followed by 31 1's) and says this number requires 32 bits to represent. I dont see why this isnt 31 (which my method computes) Can anyone explain why? And what i need to change to account for this?
0x7FFFFFFF
does require 32 bits. It could be expressed as an unsigned integer in only 31 bits:but if we interpret that as a signed integer using two's complement, then the leading
1
would indicate that it's negative. So we have to prepend a leading0
:which then makes it 32 bits.
As for what you need to change — your current program actually has undefined behavior. If
0x7FFFFFFF
(231-1) is the maximum allowed integer value, then0x7FFFFFFF + 1
cannot be computed. It is likely to result in -232, but there's absolutely no guarantee: the standard allow compilers to do absolutely anything in this case, and real-world compilers do in fact perform optimizations that can happen to give shocking results when you violate this requirement. Similarly, there's no specific guarantee what... >> 1
will mean if...
is negative, though in this case compilers are required, at least, to choose a specific behavior and document it. (Most compilers choose to produce another negative number by copying the leftmost1
bit, but there's no guarantee of that.)So really the only sure fix is either:
x
is0x7FFFFFFF
(returning a hardcoded32
) and the case thatx
is negative (replacing it with~x
, i.e.-(x+1)
, and proceeding as usual).