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
Comments (8)
- Popular
- New
- Old
You must be signed in to leave a comment
Guadalupe Gagnon
8 June 2021, 13:37
The bitwise operator '>>' (and also '<<') shift the bits of the number on the left of the operator by the number on the right times in the direction of the arrow. So:
number >> 1 - this would shift 'number' 1 bit to the right
number << 1 - this would shift 'number' 1 bit to the left
number >> 4 - this would shift 'number' 4 bits to the right
number << 4 - this would shift 'number' 4 bits to the left
So, if you take the number 146, which in binary is '10010010', and apply the operations above, here are the results:
146 >> 1 = "1001001" (this removed the last 0)
146 << 1 = "100100100" (this added a 0)
146 >> 4 = "1001" (this removed 0010 from the end)
146 << 4 = "100100100000" (this added four 0's)
+1
Guadalupe Gagnon
8 June 2021, 13:48
Next, the logical OR operator, |, (also AND '&' and XOR '^') can be applied to bits. The normal operation for OR is that in an equation if either the left or the right operator is true then the whole statement is true. This is exactly how it works on bits, with 1 being equal to 'true' and 0 equal to 'false'. So if you take two numbers, lets say 9 and 13, which in binary is "1001" and "1101", the result of "9 | 13" would be 13:
1001 - this is nine
1101 - this is 13
-------
1101 - this is the result of logical OR, which is still 13
The bitwise compliment operator, '~', functions the same way as the NOT logical operator, ' ! ', in that in changes ones to zeros and zeros to ones.
So 9, which is "1001", would become "0110"
13, which is "1101" would become "0010"
54, which is "110110" would become "001001" etc
+1
Guadalupe Gagnon
8 June 2021, 13:57
Now the algorithm above, each step of the way, starts to turn every single bit of the original number to '1'. At the line "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
+3
Guadalupe Gagnon
8 June 2021, 14:04solution
seeing is believing sometimes, here is some code:
+6
Andrei
8 June 2021, 14:28
Thanks man, it's starting to make more sense... 👍
0
Guadalupe Gagnon
8 June 2021, 14:32
Its all very logical.... though this subject really had my head spinning when I first started to learn it.
0
Andrei
8 June 2021, 15:15
In theory it would seem so, but I feel I would have to spend 1 day with a pen and paper, following each bit with the tip of my pen to understand...
0
Guadalupe Gagnon
8 June 2021, 15:21
That is almost exactly how I started to understand it. I used an excel spreadsheet to do the same thing.
+1