Looping through Bits C

Question

I'm trying to loop through the bits of an unsigned char, but I'm not sure where to start, eventually, I'll perform other bitwise operating on the bits, such as ~ and xor..etc.

Solution 1

Looping over bits can be done in several ways:

• You can do a destructive loop, when you shift the value, and test the initial or the final bit, depending on the order in which you would like to enumerate bits, or
• You can do a non-destructive loop, when you use bitwise AND to test the number with a single-bit mask, produced by left-shifting 1.

Here is an example of the first approach:

unsigned int bits = ...;
while (bits) {
    if (bits & 1) {
        // Current bit is set to 1
    } else {
        // Current bit is set to 0
    }
    bits >>= 1;
}

If you want to continue working with bits after you reach zero, make a separate counter.

Here is an example of the second approach:

unsigned int bits = ...;
for (int pos = 0 ; pos != 16 ; pos++) {
    if (bits & (1 << pos)) {
        // Current bit is set to 1
    } else {
        // Current bit is set to 0
    }
}

Solution 2

This function will allow you to iterate through all set bits in a word:

inline size_t next_bit(uint64_t bf, size_t bit) {
    return ctz(bf & ~((1UL << bit) -1));
}

The ctz function counts the number of trailing zeroes which should be provided by your compiler as a built-in function. For gcc and llvm, you can use the following (note that ctz is undefined for 0 on x86 hence the fixup):

inline size_t ctz(uint64_t x) { return x ? __builtin_ctzll(x) : 64; }

Here's an example of how to use it in a for-loop:

for (size_t i = next_bit(bf, 0); i < 64; i = next_bit(bf, i + 1))
    // the i-th bit is set.

The function works by clearing away all the bits preceding the ith bit and counting the number of trailing zeroes which will provide you with the next set bit after the ith bit. Clearing the bits is accomplished by first shifting a bit into the ith position, subtracting one which sets all the bits lower then the ith bit. We can then NOT the mask to get all the bits after i so that an AND op will remove all the bits after i. ctz does the rest.

It's a bit (pun intended) overkill for an unsigned char but I couldn't resist. Honestly, for 8-bit words, you're better off with a simple while loop as proposed in the other answers.