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

Question about the task

Resolved

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

Comments (8)

Popular
New
Old

You must be signed in to leave a comment

Guadalupe Gagnon

Level 37 , Tampa, United States

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)

Guadalupe Gagnon

Level 37 , Tampa, United States

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

Guadalupe Gagnon

Level 37 , Tampa, United States

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

Guadalupe Gagnon

Level 37 , Tampa, United States

8 June 2021, 14:04

solution

seeing is believing sometimes, here is some code:

int number = 256;
System.out.println("Starting with number '" + number +"' - in binary '" + Integer.toBinaryString(number) + "'");
number = number | (number >> 1);
System.out.println("\t" + Integer.toBinaryString(number));
number = number | (number >> 2);
System.out.println("\t" + Integer.toBinaryString(number));
number = number | (number >> 4);
System.out.println("\t" + Integer.toBinaryString(number));
number = number | (number >> 8);
System.out.println("\t" + Integer.toBinaryString(number));
number = number | (number >> 16);
System.out.println((number & ~(number >> 1)));
System.out.println(Integer.toBinaryString(number & ~(number >> 1)));