0
    int n;
    for ( n = 0; i >0; n++)
    {
        i &= (i-1);
    }
    return n;

//maybe its function is to count the number of 1, I don't know the sentence means

James
  • 2,843
  • 1
  • 14
  • 24
changjiang
  • 21
  • 1
  • 1
  • duplicate question Refer Original here: http://stackoverflow.com/q/1551500/3323444 – krishnakant Jul 28 '16 at 19:14
  • 1
    Possible duplicate of [How Does The Bitwise & (AND) Work In Java?](http://stackoverflow.com/questions/17256644/how-does-the-bitwise-and-work-in-java) – jonhopkins Jul 28 '16 at 19:15
  • @krishnakant No, this is different, it's a loop, it's not just checking to see if it's a power of 2 – James Jul 28 '16 at 19:15

3 Answers3

3

This is indeed counting the number of one-bits in the value of i. It does however only work properly for positive values. The JRE provided Integer.bitCount(i) does the same and it works in constant time as well as for negative values.

As for how it works, its hard to understand if you're not familar with binary arithmetic. What basically happens that in each loop the least significant set bit cancels out and the loop stops when all bits have been canceled out.

It does not work properly with negative values because the loops condition has been chosen poorly. It should be i != 0 instead of i > 0, then it works with negative values as well.

Durandal
  • 19,919
  • 4
  • 36
  • 70
2

& is the bitwise AND operation in Java. What this function is doing is counting the number of those operations it take to reach 0.

This function is counting the number of "1's" in a binary representation of a number (a bit of research allowed me to find this). The way this works is it flips the rightmost bit that is 1 on every pass in the loop until the number is zero.

For instance, if we run this function on 100:

1100100 & 1100011 = 1100000 //Flipped the rightmost one bit (100 & 99)
1100000 & 1011111 = 1000000 //Then the next (96 & 95)
1000000 & 0111111 = 0000000 //And finally the last (64 & 63)

So the loop will have executed 3 times, indicating 3 "on" bits in the number 100.

James
  • 2,843
  • 1
  • 14
  • 24
  • But it answers the question as written down. So maybe the answer is incomplete, but so far, it isn't wrong. – GhostCat Jul 28 '16 at 19:13
0

It means erase last bit of 1's. For example, we count # of 1's for 8. Loop1: 8 & 7.

8 = 0b1000
7 = 0b0111

We got 8 & 7 = 0. Since we only have one 1's. The result will be 1.

If we count # of 1's for 7. Loop1: 7 & 6

7 = 0b111
6 = 0b110

We got 7 & 6 = 6. As you can see, 6 = 0b110, we erase last bit of 1. Then, we count Loop2: 6 & 5

6 = 0b110
5 = 0b101

We got 6 & 5 = 4. As you can see, 4 = 0b100, we erase last bit of 1. Then, we count Loop3: 4 & 3

4 = 0b100
3 = 0b011

We got 4 & 3 = 0. Since we have three loops, the # of 1's for 7 is 3.

tony hu
  • 81
  • 1
  • 3