Bitwise Operators: Working One Bit at a Time

Kenji has eight LEDs on a board and one byte to control them. Bit 0 is the first lamp, bit 7 is the last.

He does not want eight variables. He wants one number, and a way to reach inside it.

Everything in this lesson is that: arithmetic that treats a number as a row of switches rather than a quantity.

Six operators that work on bits, not on values

Module 2 lesson 2 said an integer is a pattern of bits. These operators are the ones that admit it.

a & b      and       bit is 1 when both bits are 1
a | b      or        bit is 1 when at least one bit is 1
a ^ b      xor       bit is 1 when the two bits differ
~a         not       every bit flipped
a << n     left      every bit moves n places toward the high end
a >> n     right     every bit moves n places toward the low end

Four bits are enough to see all six. Take 12, which is 1100, and 10, which is 1010.

#include <stdio.h>

int main(void)
{
    unsigned int a = 12u;
    unsigned int b = 10u;

    printf("a & b  = %2u\n", a & b);
    printf("a | b  = %2u\n", a | b);
    printf("a ^ b  = %2u\n", a ^ b);
    printf("a << 1 = %2u\n", a << 1);
    printf("a >> 2 = %2u\n", a >> 2);
    printf("~a     = %u\n", ~a);
    return 0;
}

a & b  =  8
a | b  = 14
a ^ b  =  6
a << 1 = 24
a >> 2 =  3
~a     = 4294967283

The last line is the only surprise, and it is a width surprise. ~12 flips all 32 bits, not the four you drew.

So ~a & 15u is 3, which is the four-bit answer. Whenever you flip, you usually also mask.

A mask is a number you use as a stencil

A mask is a value whose 1 bits mark the places you care about. & with a mask keeps those places and zeroes the rest.

The mask for a single bit number k is 1u << k. That is a 1 with k zeroes after it.

Printing a byte in binary is that mask, used eight times. Module 6 writes it as a loop; today it is eight expressions.

#include <stdio.h>

int main(void)
{
    unsigned int leds = 90u;

    printf("%u%u%u%u%u%u%u%u\n",
           (leds >> 7) & 1u, (leds >> 6) & 1u,
           (leds >> 5) & 1u, (leds >> 4) & 1u,
           (leds >> 3) & 1u, (leds >> 2) & 1u,
           (leds >> 1) & 1u, leds & 1u);
    return 0;
}

01011010

Each expression shifts the bit you want down to the bottom, then keeps only that one bit.

So "read bit k" is always the same two steps: move it to the bottom, mask with 1.

Four idioms, and they are the whole lesson

Every real use of these operators is one of four lines. Learn the four and you have learned bit manipulation.

flags |=  (1u << k);      set bit k to 1
flags &= ~(1u << k);      clear bit k to 0
flags ^=  (1u << k);      toggle bit k
(flags >> k) & 1u         test bit k, worth 1 or 0

#include <stdio.h>

int main(void)
{
    unsigned int flags = 0u;

    flags |= (1u << 3);
    printf("set bit 3     %u\n", flags);
    flags |= (1u << 5);
    printf("set bit 5     %u\n", flags);
    flags &= ~(1u << 3);
    printf("clear bit 3   %u\n", flags);
    flags ^= (1u << 5);
    printf("toggle bit 5  %u\n", flags);
    printf("is bit 5 set? %u\n", (flags >> 5) & 1u);
    return 0;
}

set bit 3     8
set bit 5     40
clear bit 3   32
toggle bit 5  0
is bit 5 set? 0

Read the values as bit patterns and the arithmetic disappears. 8 is one lamp on, 40 is two lamps on, 32 is one lamp on again.

So a single unsigned int holds 32 independent yes or no answers, and each one costs one line to reach.

Shifting is multiplying, until it is not

On an unsigned value, x << n multiplies by 2 to the power n, and x >> n divides by it, throwing the remainder away.

1u << n is therefore the cheapest way to write a power of two. 1u << 10 is 1024.

Two rules stop this from being safe everywhere, and they use two different words on purpose.

• Right-shifting a negative signed value is implementation defined. The compiler must document what it does and then do it consistently. GCC keeps the sign, so -8 >> 1 is -4 there.
• Left-shifting a 1 into the sign bit is undefined behaviour. 1 << 31 on a 32-bit int has no defined meaning at all, and nothing here quotes an output for it.

Both disappear if the value is unsigned. 1u << 31 is an ordinary, fully defined 2147483648.

#include <stdio.h>

int main(void)
{
    printf("1u << 0  = %u\n", 1u << 0);
    printf("1u << 10 = %u\n", 1u << 10);
    printf("1u << 31 = %u\n", 1u << 31);
    return 0;
}

1u << 0  = 1
1u << 10 = 1024
1u << 31 = 2147483648

The u on the literal is the whole safety measure. It costs one character and removes two rules from your head.

So this track writes 1u << k every time, and shifts only unsigned values.

& is not &&, and the XOR swap is a trap

5 & 1 is 1 and 5 && 1 is also 1, which is why this mistake survives so long.

They agree by accident. 4 & 1 is 0 while 4 && 1 is 1, and there the accident ends.

& combines bits and always evaluates both sides. && combines answers and may skip the right side. Lesson 2's guarded division depends on that difference.

One more piece of famous cleverness deserves naming and then rejecting. Two numbers can be swapped with three ^= lines and no third variable.

It is real, and this track does not use it. It is slower than a third variable on any modern processor, and it is unreadable. It also produces zero, silently, when both sides name one variable. Module 2's spare box is the right answer.

#include <stdio.h>

int main(void)
{
    unsigned int n = 0;
    scanf("%u", &n);

    printf("%u\n", n & 1u);
    return 0;
}

1

#include <stdio.h>

int main(void)
{
    unsigned int bold = 0;
    unsigned int italic = 0;
    unsigned int under = 0;
    scanf("%u %u %u", &bold, &italic, &under);

    unsigned int look = (bold << 0) | (italic << 1) | (under << 2);

    printf("look %u\n", look);
    printf("italic? %u\n", (look >> 1) & 1u);
    return 0;
}

look 5
italic? 0

#include <stdio.h>

int main(void)
{
    unsigned int r = 0;
    unsigned int g = 0;
    unsigned int b = 0;
    scanf("%u %u %u", &r, &g, &b);

    unsigned int packed = (r << 16) | (g << 8) | b;

    printf("packed %u\n", packed);
    printf("r %u\n", (packed >> 16) & 255u);
    printf("g %u\n", (packed >> 8) & 255u);
    printf("b %u\n", packed & 255u);
    return 0;
}

packed 13140520
r 200
g 130
b 40

unsigned int flags = 4u;
printf("%u %u\n", flags & 1u, flags && 1u);

unsigned int nibble = 12u;
printf("%u\n", ~nibble);

printf("%d\n", 1 << 31);

unsigned int flags = 8u;
printf("%u\n", flags & (1u << 3));

unsigned int a = 1u << 31;
int b = 1 << 31;

#include <stdio.h>

int main(void)
{
    unsigned int n = 0;
    unsigned int k = 0;
    scanf("%u %u", &n, &k);

    /* Shift the bit down to the bottom, then mask with 1u. */

    return 0;
}

#include <stdio.h>

int main(void)
{
    unsigned int r = 0;
    unsigned int g = 0;
    unsigned int b = 0;
    scanf("%u %u %u", &r, &g, &b);

    /* Pack with two shifts and two ors. Unpack with shifts and 255u. */

    return 0;
}

#include <stdio.h>

int main(void)
{
    unsigned int b = 0;
    scanf("%u", &b);

    /* Eight tests, added together. No loop until Module 6. */

    return 0;
}

#include <stdio.h>

int main(void)
{
    unsigned int b = 0;
    scanf("%u", &b);

    /* Two halves: one moves up four places, the other moves down four. */

    return 0;
}

Next you find out what decides the order of all these operators when you write several of them in one line.