Step 3 of 5
Bitwise operators
Every integer is stored as a pattern of bits (binary digits, 0 or 1). The number 13 is 1101 in binary: 8 + 4 + 0 + 1. Bitwise operators work on those individual bits, all at once:
| Operator | Name | Result bit is 1 when | Example |
|---|---|---|---|
a & b |
AND | both bits are 1 | 1100 & 1010 = 1000 |
a | b |
OR | at least one is 1 | 1100 | 1010 = 1110 |
a ^ b |
XOR | the bits differ | 1100 ^ 1010 = 0110 |
~a |
NOT | the bit was 0 | flips every bit |
a << n |
shift left | bits move n places left (zeros come in) | 0011 << 2 = 1100 |
a >> n |
shift right | bits move n places right | 1100 >> 2 = 0011 |
Shifting left by n multiplies by 2 to the power n, and shifting right divides by it. 1u << n is a number with only bit n set.
#include <stdio.h>
int lowest_set_bit(unsigned x) {
for (int i = 0; i < 32; i++) {
if (x & (1u << i)) {
return i;
}
}
return -1;
}
int main(void) {
unsigned a = 12, b = 10;
printf("%u %u %u\n", a & b, a | b, a ^ b);
printf("%u %u\n", 1u << 5, 40u >> 3);
printf("%d %d\n", lowest_set_bit(12), lowest_set_bit(0));
return 0;
}
8 14 6
32 5
2 -1
Testing one bit
x & 1 is 1 if the lowest bit of x is set, else 0. More generally, x & (1u << i) is non-zero exactly when bit i is set. Combining that test with shifting (x >>= 1 moves the next bit into the lowest position) lets you look at every bit in turn.
Use unsigned types
Bit manipulation should use unsigned integers (unsigned, uint32_t). Shifting negative signed numbers, or shifting a 1 into the sign bit, is undefined or implementation-defined. The u suffix in 1u makes the literal unsigned.
Your turn: write int count_bits(unsigned x) that returns how many bits are 1. Check the lowest bit with x & 1, then shift right.