# 5.5. Debugger

> Explain what the following code does: (( n & (n-1)) == 0)

```c++
  00000010   (n)
& 00000001   (n - 1)
----------
  00000000
```

n should be odd. And if it's bigger than 2, it'll have some 1s higher up. Which won't be cleared when doing n-1. so n must be 2.

## Hints

> Start with a brute force solution. Can you try all possibilities?

n=2, but there must be something more.

> What does it mean if A & B == 0?

That A and B don't have any same bits in any position.

> If A & B == 0, then it means that A and B never have a 1 at the same spot. Apply this to the equation in the problem.

A and B are separated by 1 bit in this case, A = B + 1. It could be all 0s and 10 in the end (n=2), or 100000. So that n = pow(2,x). A power of 2.

```c++
  10000000   (n)
& 01111111   (n - 1)
----------
  00000000
```

> If ( n & ( n-1)) == 0, then this means that n and n - 1 never have a 1 in the same spot. Why would that happen?

When n is a power of 2.

> What is the relationship between how n looks and how n - 1 looks? Walk through a binary subtraction.

Yes.

> When you do a binary subtraction, you flip the rightmost 0s to a 1, stopping when you get to a 1 (which is also flipped). Everything (all the 1 s and Os) on the left will stay put.

Same answer.

> Picture n and n - 1. To subtract 1 from n, you flipped the rightmost 1 to a 0 and all the 0s on its right to 1s. If n & n -1 == 0, then there are no 1 s to the left of the first 1. What does that mean about n?

I'm getting lost.

> We know that n must have only one 1 ifn & ( n -1) == 0. What sorts ofnumbers have only one 1?

Powers of 2! Or the binary base number.

## Solution

Correct! n = a power of 2, or n=0.