why does this work? (finding odd number in c++)

Question

for (unsigned int i = 1; i <= 100; i++) {
    if (i & 0x00000001) {
        std::cout << i<<",";
    }
}

why does (and how): if( i & 0x00000001 ) figure out the odd number?

Answer 1

0x00000001 is 1 in binary, although it's written in hexadecimal (base-16) notation. That's the 0x part.

& is the bit-wise 'AND' operator, which is used to do binary digit (bit) manipulations.

i & 1 converts all of the binary digits of i to zero, except for the last one.

It's straightforward to convert the resulting 1-bit number to a boolean, for evaluation by the if statement.

The following chart shows the last 16 binary digits of i, and what happens to them.

i:   i in binary:        i & 1 in binary:    convert to boolean
---- ------------------- ------------------- ---------------------
1    0000000000000001    0000000000000001    true
2    0000000000000010    0000000000000000    false
3    0000000000000011    0000000000000001    true
4    0000000000000100    0000000000000000    false
5    0000000000000101    0000000000000001    true
6    0000000000000110    0000000000000000    false
7    0000000000000111    0000000000000001    true
8    0000000000001000    0000000000000000    false
...  ...                 ...                 ...
99   0000000001100011    0000000000000001    true
100  0000000001100100    0000000000000000    false

Answer 2

It's using a bitwise "and" operator to mask off all but the last bit. If the last bit is a 1, the number is odd. Is that enough explanation?

Answer 3

When we look at numbers in base 10, it's easy to tell if a number is divisible by 10: it has a 0 in the last position. The code above looks at the digit in the last position as well, but in base 2. If it's non-zero, the number is not divisible by 2.

Answer 4

It masks off the last bit. If you look at each place in the binary representation of a number (..., 256, 128, 64, 32, 16, 8, 4, 2, and 1), you'll notice that only the one's place is odd. All the rest of the places have an even value whether the bits are set or cleared (zero being even). And adding even numbers will always give an even number. Only that last one's place determines the parity of the number. The i & &0x00000001 part just isolates that last one's place.