C Programming Exercise – Inspect Two Consecutive Bits of Integer

learn-to-code

Question: Implement the inspect_bits function to check if any given 32-bit integer contains 2 or more consecutive ones in its binary representation. If it does, the function should return 1 otherwise it should return 0.

For example, given 13, the function should return 1 because it contains 2 consecutive ones in its binary representation (1101).

We know we can use x & (-x) to get the least significant byte (LSB) of any given integer. Therefore, the idea is to get its current LSB and compare to its previous LSB. If there are two consecutive 1 bits, the current LSB will be exactly twice big as its previous LSB. At each iteration, the LSB will be subtracted from the given input until the number becomes zero.

The C code is as follows.

1
2
3
4
5
6
7
8
9
10
11
12

int inspect_bits(unsigned int number) {
    int cur, prev = 0;
    while (number > 0) {
        cur = number & (-number);
        if (prev * 2 == cur) {
            return 1;
        }
        number -= cur;
        prev = cur;
    }
    return 0;
}

int inspect_bits(unsigned int number) {
    int cur, prev = 0;
    while (number > 0) {
        cur = number & (-number);
        if (prev * 2 == cur) {
            return 1;
        }
        number -= cur;
        prev = cur;
    }
    return 0;
}

The complexity is O(log N) because it takes at most O(log N) times to scan the bits of the integer. Any better (or other) approaches?

You may also like: C编程练习题: 判断整数是否有连续两个1

–EOF (The Ultimate Computing & Technology Blog) —