Operations on bits, getting the bigger value

Question

I'm not familiar with bitwise operations. I have this sequence:

1 0 0 0 0 : 16
---------------
0 1 1 1 1 : 15
---------------
0 1 1 1 0 : 14
---------------
.
.
.
---------------
0 0 0 1 1 :  3
---------------
0 0 0 1 0 :  2
---------------
0 0 0 0 1 :  1
---------------

I want to check first if there is more than one "1". If that's the case, I want to remove the one that has the bigger decimal value, and to finish, getting the bigger remaining. For example 15, there is four "1", I remove the bigger one, the "1" at "8", I got "0 0 1 1 1 : 7", where the bigger "1" is at "4". How can I do this?

Answer 1

Here's the code that does what you want:

unsigned chk_bits(unsigned int x) {
    unsigned i;
    if (x != 0 && (x & (x-1)) != 0) {
        /* More than one '1' bit */
        for (i = ~(~0U >> 1); (x & i) == 0; i >>= 1)
            ; /* Intentionally left blank */
        return x & ~i;
    }
    return x;
}

Note that I assume you're dealing with unsigned numbers. This is usually safer, because right shifting is implementation defined on signed integers, because of sign extension.

The if statement checks if there's more than one bit set in x. x & (x-1) is a known way to get a number that is the same as x with the first '1' least significant bit turned off (for example, if x is 101100100, then x & (x-1) is 101100000. Thus, the if says:

If x is not zero, and if turning off the first bit set to 1 (from LSB to MSB) results in something that is not 0, then...

Which is equivalent to saying that there's m ore than 1 bit set in x.

Then, we loop through every bit in x, stopping in the first most significant bit that is set. i is initialized to 1000000000000000000000000000, and the loop keeps right shifting it until x & i evaluates to something that is not zero, at which point we found the first most significant bit that is 1. At that point, taking i's complement will yield the mask to turn off this bit in x, since ~i is a number with every bit set to 1 except the only bit that was a 1 (which corresponds to the highest order bit in x). Thus, ANDing this with x gives you what you want.

The code is portable: it does not assume any particular representation, nor does it rely on the fact that unsigned is 32 or 64 bits.

UPDATE: I'm adding a more detailed explanation after reading your comment.

1st step - understanding what x & (x-1) does:

We have to consider two possibilities here:

• x ends with a 1 (.......0011001)
• x ends with a 0 (.......0011000)

In the first case, it is easy to see that x-1 is just x with the rightmost bit set to 0. For example, 0011001 - 1 = 0011000, so, effectively, x & (x-1) will just be x-1.

In the second case, it might be slightly harder to understand, but if the rightmost bit of x is a 0, then x-1 will be x with every 0 bit switched to a 1 bit, starting on the least significant bits, until a 1 is found, which is turned into a 0.

Let me give you an example, because this can be tricky for someone new to this:

1101011000 - 1 = 11101010111

Why is that? Because the previous number of a binary number ending with a 0 is a binary number filled with one or more 1 bits in the rightmost positions. When we increment it, like 10101111101111 + 1, we have to increment the next "free" position, i.e., the next 0 position, to turn it into a 1, and then all of the 1-bits to the right of that position are turned into 0. This is the way ANY base-n counting works, the only difference is that for base-2 you only have 0's and 1's.

Think about how base-10 counting works. When we run out of digits, the value wraps around and we add a new digit on the left side. What comes after 999? Well, the counting resets again, with a new digit on the left, and the 9's wrap around to 0, and the result is 1000. The same thing happens with binary arithmetic.

Think about the process of counting in binary; we just have 2 bits, 0 and 1:

• 0 (decimal 0)
• 1 (decimal 1 - now, we ran out of bits. For the next number, this 1 will be turned into a 0, and we need to add a new bit to the left)
• 10 (decimal 2)
• 11 (decimal 3 - the process is going to repeat again - we ran out of bits, so now those 2 bits will be turned into 0 and a new bit to the left must be added)
• 100 (decimal 4)
• 101 (decimal 5)
• 110 (the same process repeats again)
• 111
• ...

See how the pattern is exactly as I described?

Remember we are considering the 2nd case, where x ends with a 0. While comparing x-1 with x, rightmost 0's on x are now 1's in x-1, and the rightmost 1 in x is now 0 in x-1. Thus, the only part of x that remains the same is that on the left of the 1 that was turned into a 0.

So, x & (x-1) will be the same as x until the position where the first rightmost 1 bit was. So now we can see that in both cases, x & (x-1) will in fact delete the rightmost 1 bit of x.

2nd step: What exactly is ~0U >> 1?

The letter U stands for unsigned. In C, integer constants are of type int unless you specify it. Appending a U to an integer constant makes it unsigned. I used this because, as I mentioned earlier, it is implementation defined whether right shifting makes sign extension. The unary operator ~ is the complement operator, it grabs a number, and takes its complement: every 0 bit is turned into 1 and every 1 bit is turned into 0. So, ~0 is a number filled with 1's: 11111111111.... Then I shift it right one position, so now we have: 01111111...., and the expression for this is ~0U >> 1. Finally, I take the complement of that, to get 100000...., which in code is ~(~0U >> 1). This is just a portable way to get a number with the leftmost bit set to 1 and every other set to 0.

You can give a look at K&R chapter 2, more specifically, section 2.9. Starting on page 48, bitwise operators are presented. Exercise 2-9 challenges the reader to explain why x & (x-1) works. In case you don't know, K&R is a book describing the C programming language written by Kernighan and Ritchie, the creators of C. The book title is "The C Programming Language", I recommend you to get a copy of the second edition. Every good C programmer learned C from this book.

Answer 2

I want to check first if there is more than one "1".

If a number has a single 1 in its binary representation then it is a number that can be represented in the form 2^x. For example,

4     00000100   2^2  
32    00010000   2^5

So to check for single one, you can just check for this property.

If log₂ (x) is a whole number then it has single 1 in it's binary representation.

You can calculate log₂ (x)

log₂ (x) = log_y (x) / log_y (2)

where y can be anything, which for standard log functions is either 10 or e.

Here is a solution

double logBase2 = log(num)/log(2);   
if (logBase2 != (int)logBase2) {

    int i = 7;
    for (;i >0 ; i--) {

        if (num & (1 << i)) {

            num &= ~(1 << i);
            break;
        }
    }
}