58 lines
1.7 KiB
Markdown
58 lines
1.7 KiB
Markdown
# 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.
|