Rank 02 Quick n Dirty - kevshouse/exam_quest GitHub Wiki

is_power_of_2(unsigned int n)
{
    return ((n & (-n)) == n ? 1 : 0);
}

This C function checks if a number is a power of 2 using a clever bit manipulation trick. Here's how it works: The core logic: (n & (-n)) == n For any number that's a power of 2, this expression will be true. Here's why:

Powers of 2 in binary have exactly one bit set:

1 = 0001 2 = 0010 4 = 0100 8 = 1000

Two's complement negation (-n) flips all bits and adds 1:

If n = 4 (0100), then -n = 1100 If n = 8 (1000), then -n = 1000

The bitwise AND (n & (-n)) isolates the rightmost set bit:

• For n = 4: 0100 & 1100 = 0100 (which equals n)
• For n = 8: 1000 & 1000 = 1000 (which equals n)

For non-powers of 2,

• multiple bits are set, so n & (-n) gives only the rightmost bit:
  

 -n = 1010,
   so 0110
    & 1010 = 0010 (not equal to 6)

Special cases:

• Returns 1 when n = 0 (since 0 & 0 = 0), though 0 isn't typically considered a power of 2
• Works correctly for all positive powers of 2
• The ternary operator ? 1 : 0 converts the boolean result to an integer (1 for true, 0 for false).
• This is much more efficient than division or logarithm-based approaches since it uses only bitwise operations.