# Complexity of n & (n - 1) should be O(1) or O(log n)?

I'm looking at the methods posted in https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ for checking whether n is a power of 2.

Method 5, pasted below, in the link claims to be O(1) but shouldn't it be O(log n)? When we do n & (n - 1), that's a bitwise operation over 32 bits (since n is a 32 bit integer), right?

bool isPowerOfTwo (int x)
{
/* First x in the below expression is for the case when x is 0 */
return x && (!(x&(x-1)));
}


Method 2, pasted below, claims to be O(log n), which I am not sure if it's correct either. The number of while loops is O(log n) and each while loop iteration is O(log n) (because we're bitwise-and'ing log n bits), so shouldn't it be O(log^2 n)?

bool isPowerOfTwo(int n)
{
if (n == 0)
return 0;
while (n != 1)
{
if (n%2 != 0)
return 0;
n = n/2;
}
return 1;
}


I always get a bit confused with complexity analysis on the bit-scale.

• Can you make your question self-contained? Also what cost model do you want to use? Also notice that if you fix an upper bound on the number of bits of $n$ (e.g., $32$), then any algorithm that terminates will necessarily take at most constant time (simply chose any constant not smaller than the maximum time needed when the algorithm is executed with inputs $0, 1, \dots, 2^{32}-1$). Jul 19 '21 at 20:39
• @Steven Just made it self-contained. Let me check your cost model link and get back to you on that. I'm not well versed with complexity analysis -- I'm primarily just trying to learn enough to pass data structures and algorithms interviews (so nothing in depth). Jul 19 '21 at 20:43
• @Steven By your logic of fixing the upper bound, then both algorithms in the OP would be O(1) space and time right? Jul 19 '21 at 20:44
• Right. But you probably want to analyze the running time of the algorithm as a function of $n$, when $n$ grows. I..e, you are interested in the asymptotic running time of the algorithm. Jul 19 '21 at 20:44
• @Steven Hmmm I'm not exactly sure which model is used. I think the uniform model may be what is used in interviews, but when it comes to bit manipulation questions, maybe the log model is used. So maybe we can analyze the complexity separately under each model? For method 2 in the OP, I think it's O(log n) under the uniform model and O(log^2 n) under the log model, and then method 5 seems to be O(1) and O(log n) under the uniform and log models, resp. Jul 19 '21 at 20:46

In the RAM model with uniform costs and word size $$\Omega(\log n)$$ the first algorithm requires $$O(1)$$ time since each word operation takes constant time.
The second algorithm requires time $$O(\log n)$$ since each iteration can be performed in $$O(1)$$ time and there are at most $$O(\log n)$$ iterations (after each iteration the value of $$n$$ is at most half the previous value).
If you want to use logarithmic cost model, then the first algorithm takes linear time in the number of bits of $$n$$, i.e., $$O( \log n)$$ time. The second algorithm (as written) takes $$O(\log n)$$ time per iteration to perform the comparison and to shift all the bits towards the right (this is the n=n/2 operation). The number of iterations is $$O(\log n)$$ as before. The overall running time is $$O(\log^2 n)$$.
All running times in this answer are tight (in the sense that if I said that an algorithm requires $$O(f(n))$$ time then there is a suitable infinite family of inputs that cause the algorithm to require $$\Omega(f(n))$$ time).
Well, in theory the first one is $$O(\log n)$$. In practice, if $$n < 2^{64}$$ for example, it is a fixed number of operations on a 64 bit processor. Likely to cost 1 or at most 2 nanoseconds. (And I would write it as (x & (x-1)) == 0 && x != 0, so the comparison x != 0 isn't done for all numbers, but only for numbers that are either powers of two or equal to 0). If n can be large, say 100s of bits, then for every 64 bit in n you have the same cost again.
And in theory, the second one is $$O(\log^2 n)$$, while in practice it is $$O(\log n)$$. Same reasoning.