Loading…

Can you explain the code ((n & (n – 1)) == 0)

 

Let’s start from the very beginning.

 

What does A & B == 0 mean?

 

Actually, it means that A and B do not contain single bits at the same positions. In case n & (n – 1) == 0, then n and n – 1 do not have common units.

 

What does n – 1 similar to (compared to n)?

 

Currently, try to do manual subtraction (binary or decimal systems).

 

What will happen?

 

Once you subtract 1, look at the low bit. It means that you replace 1 with 0. However, if there is 0, then you have to borrow from the high bit. You change every bit from 0 to 1 until you get to 1. Then you invert the unit to zero, you’re done.

 

Thus, we can say that n – 1 will coincide with n in some bits, except that the lower zeros in n correspond to units in n – 1, and the last single bit in n becomes zero in n – 1.

 

What does n & (n – 1) == 0 mean?

 

n and n – 1 do not contain common units. Let’s suppose they are the following:

 

  • n = abcde1000

  • n – 1 = abcde0111

 

Thus, abcde must be zero bits, n is of the form 000001000. This way, the value of n is a power of two.

 

Finally, here is our answer: the logical expression ((n & (n-1)) == 0) is true if n is a power of two or is equal to zero.

 


Leave a Comment