Bitwise operators

Lesson 29 of 30 · Part 6 · Going further · about 15 minutes

Inside the computer, every whole number is a row of bits: zeros and ones. The bitwise operators work on those bits directly. To see them, here's a small function of our own that shows the last 8 bits of a number (printf has no format specifier for binary):

1#include <stdio.h>2 3void print_bits(unsigned int x) {4    for (int i = 7; i >= 0; i--) {5        int bit = (x >> i) & 1;6        printf("%d", bit);7    }8    printf("\n");9}10 11int main(void) {12    int numbers[5] = {1, 2, 5, 13, 255};13    for (int i = 0; i < 5; i++) {14        printf("%3d = ", numbers[i]);15        print_bits(numbers[i]);16    }17    return 0;18}

  1 = 00000001
  2 = 00000010
  5 = 00000101
 13 = 00001101
255 = 11111111

unsigned int is an int that can't be negative; it's the usual type for working with bits. How print_bits works will make sense by the end of this lesson. For now, just look at what it prints.

Binary

In the numbers you use every day, each place is worth 10 times the one on its right: ones, tens, hundreds. In binary, each place is worth 2 times the one on its right. Here is 13 in 8 bits:

The places with a 1 are 8, 4 and 1, and 8 + 4 + 1 = 13. With 8 bits, the largest number is all ones: 128 + 64 + ... + 1 = 255. An int has 32 bits; here we show only the last 8, because they're enough for small numbers.

People count bits from the right, starting at 0: bit 0 is worth 1, bit 1 is worth 2, bit 2 is worth 4, and so on.

& and |

& (and) and | (or) compare two numbers bit by bit, one place at a time:

& gives 1 only where both have a 1; | gives 1 where either has a 1. (^ is in the next section.)

1#include <stdio.h>2 3void print_bits(unsigned int x) {4    for (int i = 7; i >= 0; i--) {5        int bit = (x >> i) & 1;6        printf("%d", bit);7    }8    printf("\n");9}10 11int main(void) {12    int a = 12;13    int b = 10;14    printf("a     = ");15    print_bits(a);16    printf("b     = ");17    print_bits(b);18    printf("a & b = ");19    print_bits(a & b);20    printf("a | b = ");21    print_bits(a | b);22    printf("%d %d\n", a & b, a | b);23    return 0;24}

a     = 00001100
b     = 00001010
a & b = 00001000
a | b = 00001110
8 14

Don't mix them up with && and || (lesson 5). Those look at whole values, true or false, and give 1 or 0. 12 && 10 is 1, but 12 & 10 is 8.

^ and ~

^ (exclusive or, often called xor) gives 1 where the two bits are different. Doing ^ b twice gives you back what you started with. ~ takes just one number and flips every bit: 0 becomes 1, and 1 becomes 0.

1#include <stdio.h>2 3void print_bits(unsigned int x) {4    for (int i = 7; i >= 0; i--) {5        int bit = (x >> i) & 1;6        printf("%d", bit);7    }8    printf("\n");9}10 11int main(void) {12    int a = 12;13    int b = 10;14    printf("a ^ b       = ");15    print_bits(a ^ b);16    printf("(a ^ b) ^ b = ");17    print_bits((a ^ b) ^ b);18    printf("~a          = ");19    print_bits(~a);20    return 0;21}

a ^ b       = 00000110
(a ^ b) ^ b = 00001100
~a          = 11110011

~a flips all 32 bits, not just the 8 shown here, so as an int it's a negative number. On its own it's rarely useful; you'll see what it's good for in the section on flags.

Shifting: << and >>

x << n moves every bit n places to the left and fills in zeros on the right. Each place to the left is worth twice as much, so shifting left by 1 multiplies by 2. x >> n moves the bits to the right; the bits that fall off the end are lost, so it divides by 2 and drops the remainder.

1#include <stdio.h>2 3int main(void) {4    for (int i = 0; i < 8; i++) {5        printf("%d ", 1 << i);6    }7    printf("\n");8    printf("%d %d %d\n", 5 << 1, 5 << 2, 5 << 3);9    printf("%d %d %d\n", 40 >> 1, 40 >> 2, 41 >> 1);10    return 0;11}

1 2 4 8 16 32 64 128 
10 20 40
20 10 20

1 << i is a number with only bit i set: 1, 2, 4, 8, and so on. You'll use that a lot. Now print_bits makes sense too: x >> i moves bit i to the far right, and & 1 keeps only that last bit.

1#include <stdio.h>2 3int main(void) {4    printf("%d\n", 3 << 4);5    return 0;6}

Shift only by less than the number of bits (fewer than 32 for an int), and don't shift negative numbers left: both are undefined behavior.

Odd or even

A number's bit 0 is worth 1, and every other place is worth an even amount. So a number is odd exactly when its bit 0 is 1, and n & 1 tells you which:

1#include <stdio.h>2 3int main(void) {4    int numbers[5] = {7, 10, 23, 64, 0};5    for (int i = 0; i < 5; i++) {6        if (numbers[i] & 1) {7            printf("%d is odd\n", numbers[i]);8        } else {9            printf("%d is even\n", numbers[i]);10        }11    }12    return 0;13}

7 is odd
10 is even
23 is odd
64 is even
0 is even

n % 2 == 1 does the same job for numbers that aren't negative. Use whichever reads more clearly to you; the compiler often turns both into the same thing.

A set of switches in one int

A file can be readable, writable and runnable, each one yes or no. Instead of three variables, give each one its own bit, and keep them all in one int. Each name is a number with just one bit set (with #define from lesson 28):

1#include <stdio.h>2 3#define READ (1 << 0)4#define WRITE (1 << 1)5#define RUN (1 << 2)6 7void show(int perms) {8    char text[] = "---";9    if (perms & READ) {10        text[0] = 'r';11    }12    if (perms & WRITE) {13        text[1] = 'w';14    }15    if (perms & RUN) {16        text[2] = 'x';17    }18    printf("%s  (%d)\n", text, perms);19}20 21int main(void) {22    int perms = READ | WRITE;23    show(perms);24    perms |= RUN;25    show(perms);26    perms &= ~WRITE;27    show(perms);28    perms ^= READ;29    show(perms);30    return 0;31}

rw-  (3)
rwx  (7)
r-x  (5)
--x  (4)

~WRITE has every bit set except the WRITE bit, so & ~WRITE turns off that one bit and keeps the rest. Press Step and watch perms change from 3 to 7 to 5 to 4.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it.

45 has 4 ones

1#include <stdio.h>2 3int main(void) {4    int n = 45;5 6    return 0;7}

2 times: 300
8 times: 1200
half: 75

1#include <stdio.h>2 3int main(void) {4    int price = 150;5 6    return 0;7}

sound: off
dark: on
alerts: on

1#include <stdio.h>2 3#define SOUND (1 << 0)4#define DARK (1 << 1)5#define ALERTS (1 << 2)6 7int main(void) {8    int settings = SOUND | DARK;9 10    if (settings & SOUND) {11        printf("sound: on\n");12    } else {13        printf("sound: off\n");14    }15    if (settings & DARK) {16        printf("dark: on\n");17    } else {18        printf("dark: off\n");19    }20    if (settings & ALERTS) {21        printf("alerts: on\n");22    } else {23        printf("alerts: off\n");24    }25    return 0;26}

What you learned

• A whole number is a row of bits; in binary each place is worth twice the one on its right (1, 2, 4, 8 ...).
• & keeps bits that are 1 in both, | in either, ^ in exactly one; ~ flips every bit. They aren't && and ||.
• x << n multiplies by 2 n times; x >> n divides by 2 n times and drops the remainder. 1 << i has only bit i set.
• n & 1 is 1 for odd numbers and 0 for even ones.
• Flags in one int: turn on with |=, off with &= ~, flip with ^=, and check with &.