Find if a number is a power of two
October 21, 2009I took a midterm today, for one of my programming classes, and realized what I could have given as at least a partial answer to one of the questions a few minutes too late. And so, I have a need to write it down in full somewhere.
The question was, how to find if a number is a power of two, using only bitwise operators, and no more than 40; and without any constants larger than 8 bits. (We could use & | ^ ! + >> << ~) *Note: negative numbers were considered excluded, and so should return 0. Only positive numbers that were powers of two should return 1.
isPowerOfTwo(int x) {
int y = 31 - (x >> 1);
return ( ((x<<y) >> 31) & 1);
}
I am still not sure exactly where to go with this. Bummer, because earlier I thought it would be the solution, but only when I typed it out now did I see the problem with it… Instead, it seems to return if the bit at the specified power of two is a 0 or a 1? I’m not sure exactly, and I’m supposed to be writing an essay, not writing code, so I can’t take the time to figure out what it does or the correct solution right now. It is bugging me…
*Random other side thought: I had to include the “CPP” in the C++ category, because apparently WordPress does not recognize a difference between “C++” and “C” as the category name; and it thought I was trying to add the same category twice. It probably normally doesn’t make a difference, but there are instances where code is not compatible between C and C++, and well…that’s not even getting into C#.
