Bit manipulation · about 45 min

Bitwise operators and shifts

Why this matters

So far you have treated integers as numbers. Bitwise operators let you treat them as what they physically are: rows of bits. That is how hardware registers are programmed, how file permissions (rwxr-xr-x) are stored, how network protocols pack fields into headers, how compression and cryptography work, and how many fast algorithms squeeze sets of flags into a single word. The operators are simple; using them confidently takes practice with the binary picture in your head.

The picture

Recall from the types module that an unsigned char is 8 bits and bit 0 is the least significant (rightmost):

  bit:     7   6   5   4   3   2   1   0
  value: 128  64  32  16   8   4   2   1

  0xCA  =  1   1   0   0   1   0   1   0   = 128 + 64 + 8 + 2 = 202

Hexadecimal is the natural notation for bits because each hex digit is exactly four bits: 0xCA is 1100 1010. Get used to reading hex this way; it is why programmers prefer it.

The six operators

Each bitwise operator works on every bit position independently (except the shifts):

  operator  name          result bit is 1 when     a = 1100 1010, b = 0101 1100
  a & b     AND           both bits are 1          0100 1000
  a | b     OR            either bit is 1          1101 1110
  a ^ b     XOR           the bits differ          1001 0110
  ~a        complement    the bit was 0            0011 0101
  a << n    left shift    bits move n places left, zeros enter on the right
                                                   a << 2 = 0010 1000 (8-bit view)
  a >> n    right shift   bits move n places right a >> 2 = 0011 0010

The compound forms &=, |=, ^=, <<= and >>= work like +=.

Here is a program that prints these with a small helper:

#include <stdio.h>

void print_bits(unsigned char x)
{
    for (int i = 7; i >= 0; i--)
        putchar((x >> i) & 1u ? '1' : '0');
    putchar('\n');
}

int main(void)
{
    unsigned char a = 0xCA;   /* 1100 1010 */
    unsigned char b = 0x5C;   /* 0101 1100 */
    print_bits(a & b);
    print_bits(a | b);
    print_bits(a ^ b);
    print_bits((unsigned char)~a);
    print_bits((unsigned char)(a << 2));
    print_bits(a >> 2);
    return 0;
}

print_bits is worth understanding fully: x >> i moves bit i down to position 0, and & 1u throws away every other bit, leaving 0 or 1. This "shift then mask" idiom extracts any bit.

Note: operands narrower than int are promoted to int before any arithmetic, including bitwise operations. ~a on an unsigned char 0xCA is computed as the int ~202, which is -203 (0xFFFFFF35). The cast back to unsigned char keeps only the low 8 bits. This is why bit manipulation is usually done on unsigned int or the fixed-width types like uint32_t.

Logical versus bitwise

&&, || and ! treat a whole value as true (nonzero) or false (zero) and produce 0 or 1. &, | and ~ work bit by bit and produce any value:

12 && 10    /* 1: both are nonzero */
12 & 10     /* 8: 1100 & 1010 = 1000 */
!12         /* 0 */
~12u        /* 4294967283: every bit flipped */

&& and || also short-circuit (stop evaluating as soon as the answer is known); & and | always evaluate both sides. Mixing them up is a classic bug that compiles silently.

Shifts are multiplication and division by powers of two

Shifting left by n multiplies by 2^n; shifting an unsigned value right by n divides by 2^n, discarding the remainder:

1u << 4      /* 16 */
5u << 3      /* 40 */
0x80u >> 3   /* 16 */
200u >> 1    /* 100 */

Bits shifted out of either end are lost. Shifts are cheap, but do not write x << 3 to mean x * 8 for speed: compilers already do that, and x * 8 says what you mean.

Signed shifts: rules to remember

Right-shifting a negative number is implementation-defined. gcc does an arithmetic shift, copying the sign bit in from the left, so -16 >> 2 is -4. Note that it rounds toward negative infinity: -17 >> 2 is -5, while -17 / 4 is -4.
Left-shifting a negative number, or shifting a 1 into or past the sign bit, is undefined behavior: 1 << 31 with a 32-bit int is UB. Write 1u << 31.
Shifting by a negative amount, or by at least the width of the type (x << 32 for a 32-bit x) is undefined, and on x86 really does give strange results because the CPU only uses the low 5 bits of the count.

The simple rule: do bit manipulation on unsigned types, and write constants with a u suffix.

Precedence

The bitwise operators have surprisingly low precedence, below the comparisons:

  highest   ~  !  (unary)
            *  /  %
            +  -
            <<  >>
            <  <=  >  >=
            ==  !=
            &
            ^
            |
            &&
  lowest    ||   ?:   =

So x & 1 == 0 means x & (1 == 0), and 1 << n + 1 means 1 << (n + 1). gcc warns about the first (-Wparentheses). The cure is always the same: parenthesize every bitwise subexpression, (x & 1) == 0.

Common mistakes

Using & where && was meant, or vice versa. if (flags & READ && flags & WRITE) happens to work; if (a & b) with a = 1, b = 2 is false even though both are "true".

Forgetting the precedence rules. Read the warning:

warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]

Shifting signed values, especially 1 << 31. Use 1u << 31.
Shifting by the full width to "clear" a value: x >> 32 is UB for a 32-bit x, not 0.
Expecting ~ on a small type to stay small: ~(unsigned char)0 is the int -1, not 255.

Recap

& (both), | (either), ^ (different) and ~ (flip) operate on each bit; << and >> move bits.
(x >> i) & 1 extracts bit i.
Left shift multiplies by 2^n, right shift of unsigned divides by 2^n.
Shifting signed values into the sign bit, or by the full width or more, is undefined; use unsigned types and u constants.
Bitwise operators bind more loosely than ==: parenthesize.

Going further: in <stdint.h>, uint8_t, uint16_t, uint32_t and uint64_t give exact widths for bit work. Print a uint32_t in hex with printf("%08x\n", value) and try predicting the results of a few shifts before running them.

Exercises

Exercise 1 · quiz

Predict the results

What does this print?

unsigned a = 12, b = 10;     /* 1100 and 1010 in binary */
printf("%u %u %u %u\n", a & b, a | b, a ^ b, a >> 2);

8 14 6 3
1 1 0 3
22 14 2 48
8 14 2 6

Answer

8 14 6 3

1100 & 1010 = 1000 = 8 (bits set in both). 1100 | 1010 = 1110 = 14 (bits set in either). 1100 ^ 1010 = 0110 = 6 (bits set in exactly one). 1100 >> 2 = 0011 = 3 (shifting right by n divides an unsigned value by 2^n, rounding down). Do not confuse & and | with the logical && and ||, which only produce 0 or 1: 12 && 10 is 1.

Exercise 2 · quiz

The precedence trap

x is 6. What does if (x & 1 == 0) test?

Whether x is even, as intended
x & (1 == 0), which is x & 0, which is always 0: the branch is never taken
(x & 1) == 0, because & binds tighter than ==
It does not compile

Answer

x & (1 == 0), which is x & 0, which is always 0: the branch is never taken

In C, == binds tighter than &, |, and ^ (a historical accident from before && existed). So x & 1 == 0 parses as x & (1 == 0), that is x & 0, always false. gcc warns "suggest parentheses around comparison in operand of '&'". Always parenthesize bitwise expressions inside comparisons: (x & 1) == 0.

Exercise 3 · write code

Print in binary

printf has no binary conversion, so write one. The program reads unsigned integers from stdin until end of input (each between 0 and 255) and prints each as exactly 8 binary digits, most significant bit first, one per line. For input 5 255 0 128 the output is:

Use shifts and & to extract each bit; do not use division or arrays of strings.

File: main.c

Starting point

#include <stdio.h>

int main(void)
{
    unsigned x;
    while (scanf("%u", &x) == 1) {
        /* print the 8 bits of x, highest first, then a newline */
    }
    return 0;
}

Example

input

5 255 0 128

expected output

Example

input

202 92 1

expected output

11001010
01011100
00000001

Hint 1

Bit number i (counting from 0 at the right) is (x >> i) & 1.

Hint 2

Loop i from 7 down to 0 and print '1' or '0' for each bit.

Reference solution

#include <stdio.h>

int main(void)
{
    unsigned x;
    while (scanf("%u", &x) == 1) {
        for (int i = 7; i >= 0; i--)
            putchar((x >> i) & 1u ? '1' : '0');
        putchar('\n');
    }
    return 0;
}

Exercise 4 · write code

Count the set bits

Write int count_bits(unsigned x) that returns how many bits of x are 1 (the "population count"). For example count_bits(0) is 0, count_bits(7) is 3 and count_bits(0xFFFFFFFF) is 32. Use a loop with & and >>; do not use compiler builtins.

main reads unsigned integers until end of input and prints each count on its own line.

File: main.c

Starting point

#include <stdio.h>

int count_bits(unsigned x)
{
    int count = 0;
    /* your loop here */
    return count;
}

int main(void)
{
    unsigned x;
    while (scanf("%u", &x) == 1)
        printf("%d\n", count_bits(x));
    return 0;
}

Example

input

0 7 4294967295 1024

expected output

Hint 1

Look at the lowest bit with x & 1, then shift x right by one and repeat.

Hint 2

Stop when x becomes 0: there are no more 1 bits.

Reference solution

#include <stdio.h>

int count_bits(unsigned x)
{
    int count = 0;
    while (x != 0) {
        count += x & 1u;
        x >>= 1;
    }
    return count;
}

int main(void)
{
    unsigned x;
    while (scanf("%u", &x) == 1)
        printf("%d\n", count_bits(x));
    return 0;
}