```
number = number | (number >> 1);
number = number | (number >> 2);
number = number | (number >> 4);
number = number | (number >> 8);
number = number | (number >> 16);
return (number & ~(number >> 1));
```

Andrei

Level 41

# Why 1 2 4 8 16? Can someone please explain the algorithm?

Resolved

number = number | (number >> 16);", this completes it the binary of the number, starting from the highest bit of the original number down to the lowest bit will be all '1'. So 9, which was "1001" will be "1111". 19519, which in binary is "100110000111111" becomes "111111111111111" etc The last line "(number & ~(number >> 1)" will shift the number one bit to the right, which means the string of ones becomes one zero followed by ones. then it flips the bits so zeros become ones and ones become zeros, then it does a logical AND on that and the original number. So the result of the second to last line on 9, which was "1001", is will be "1111". Doing first (number >> 1) makes that number "0111". Then applying the '~' operator to that flips all the bits so the number becomes "...1111000" (that would be ones to the left until the number was 32 bits). Doing a logical and on that would equal 8, or binary "1000" : ....11111000 & 1001 ---------------- 1000