Tell if a 32 bit signed int is a power of 2

Question

I need to determine if a signed 32 bit number is a power of two. So far I know the first thing to do is check if its negative since negative numbers cannot be powers of 2. Then I need to see if the next numbers are valid etc... SO I was able to write it like this:

// Return 1 if x is a power of 2, and return 0 otherwise.
int func(int x)
{
     return ((x != 0) && ((x & (~x + 1)) == x));
}

But for my assignment I can only use 20 of these operators:

! ~ & ^ | + << >>

and NO equality statements or loops or casting or language constructs.

So I am trying to convert the equality parts and I know that !(a^b) is the same as a == b but I cant seem to figure it out completely. Any ideas on how to covert that to the allowed operators?

Answer 1

Tim's comment ashamed me. Let me try to help you to find the answer by yourself.

What does it mean that x is power of 2 in terms of bit manipulation? It means that there is only one bit set to 1. How can we do such a trick, that will turn that bit to 0 and some other possibly to 1? So that & will give 0? In single expression? If you find out - you win.

Answer 2

Try these ideas:

• ~!!x+1 gives a mask: 0 if x==0 and -1 if x!=0.
• (x&(~x+1))^x gives 0 if x has at most 1 bit set and nonzero otherwise, except when ~x is INT_MIN, in which case the result is undefined... You could perhaps split it into multiple parts with bitshifts to avoid this but then I think you'll exceed the operation limit.
• You also want to check the sign bit, since negative values are not powers of two...

BTW, it sounds like your instructor is unaware that signed overflow is UB in C. He should be writing these problems for unsigned integers. Even if you want to treat the value semantically as if it were signed, you need unsigned arithmetic to do meaningful bitwise operations like this.

Answer 3

First, in your solution, it should be

return ((x > 0) && ((x & (~x + 1)) == x));

since negative numbers cannot be the power of 2. According to your requirement, we need to convert ">", "&&", "==" into permitted operators.

First think of ">", an integer>0 when its sign bit is 1 and it is not 0; so we consider

~(x >> 31) & (x & ~0)

this expression above will return a non zero number if x is non-positive. Notice that ~0 = -1, which is 0x11111111. We use x & ~0 to check if this integer is all 0 at each digit.

Secondly we consider "&&". AND is pretty straight forward -- we only need to get 0x01 & 0x01 to return 1. So here we need to add (!!) in front of our first answer to change it to 0x01 if it returns a nonzero number.

Finally, we consider "==". To test equity of A and B we only need to do

!(A ^ B)

So finally we have

return (!!(~(x >> 31) & (x & ~0))) & (!((x&(~x+1)) ^ x))

It seems that it's a homework problem. Please don't simply copy and paste. My answer is kind of awkward, it might be improved.

Answer 4

int ispower2(int x)
{

    int ispositive= ! ( (x>>31) ^ 0) & !!(x^0);         
    int temp= !((x & ~x+1) ^ x);
    return temp & ispositive;

}

Answer 5

Think about this... any power of 2 minus 1 is a string of 0s followed by a string of 1s. You can implement minus one by x + ~0. Think about where the string of 1s starts with relation to the single 1 that would be in a power of 2.

Answer 6

It is interesting and efficient to use bitwise operators in C to solve some problems. In this question, we need to deal with two checks:

1. the sign check. If negative, return 0; otherwise return 1;

   ! (x >> 31 & ox1) & !(!x)

   /* This op. extracts the sign bit in x. However, the >> in this case will be arithmetic. That means there will be all 1 before the last bit(LSB). For negative int, it is oxFFFFFFFF(-); otherwise, oxFFFFFFFE(+). The AND ox1 op. corrects the >> to ox1(-) or ox0(+). The Logical ! turns ox1(-) and ox0 (+) into 0 or 1,respectively. The !(!x) makes sure 0 is not power(2)*/

2. the isPower(2) check. If yes, return 1; otherwise 0.

   !( x & (~x + ox1) ^ x )

   /* This op. does the isPower(2) check. The x & (~x + ox1) returns x, if and only if x is power(2). For example: x = ox2 and ~x + ox1 = oxFFFFFFFE. x & (~x + ox1) = ox2; if x = ox5 and ~x + ox1 = oxFFFFFFFB. x & (~x + ox1) = ox1. Therefore, ox2 ^ ox2 = 0; but ox5 ^ ox1 = ox4. The ! op turn 0 and others into 1 and 0, respectively.*/

The last AND op. between 1 and 2 checks will generate the result of isPower(2) function.