Bit manipulation
An integer is a row of bits, and C lets you address them. The operators are &, |, ^ and ~, with << and >> to move bits. The widths they operate on were fixed in lesson 6; here the bits themselves become the subject.
Bits and hexadecimal
Hexadecimal is the readable spelling of bits: one digit is exactly four bits, so two digits are one byte. Printing a value with %X and shifting it out bit by bit shows the same number in both forms. The loop counts down from the top bit so the output reads left to right.
#include <stdio.h>
int main(void)
{
for (unsigned int value = 0; value < 16; value++) {
printf("%2u %2X ", value, value);
for (int bit = 3; bit >= 0; bit--) {
putchar(((value >> bit) & 1u) ? '1' : '0');
}
putchar('\n');
}
return 0;
}
gcc -Wall -Wextra hex.c -o hex
./hex
0 0 0000
1 1 0001
2 2 0010
3 3 0011
4 4 0100
5 5 0101
6 6 0110
7 7 0111
8 8 1000
9 9 1001
10 A 1010
11 B 1011
12 C 1100
13 D 1101
14 E 1110
15 F 1111
The mask 1u is unsigned, so the shift and the & stay in unsigned arithmetic. Writing plain 1 would work here as well, but on the top bit of a signed value it would not, which the last section shows.
Shifts
x << n multiplies by 2n and x >> n divides by it, as long as no set bit is shifted out. A right shift of an unsigned value fills with zeros. On a signed negative value the fill is implementation-defined, so this course shifts unsigned values when the bit pattern matters.
#include <stdio.h>
int main(void)
{
unsigned int one = 1;
for (int n = 0; n < 8; n++) {
printf("1 << %d = %u\n", n, one << n);
}
printf("0xA5 >> 4 = %u\n", 0xA5u >> 4);
printf("0xA5 & 0x0F = %u\n", 0xA5u & 0x0Fu);
return 0;
}
gcc -Wall -Wextra shifts.c -o shifts
./shifts
1 << 0 = 1
1 << 1 = 2
1 << 2 = 4
1 << 3 = 8
1 << 4 = 16
1 << 5 = 32
1 << 6 = 64
1 << 7 = 128
0xA5 >> 4 = 10
0xA5 & 0x0F = 5
The last two lines split a byte into two nibbles: 0xA5 is 1010 0101, the high nibble is 10 and the low one is 5. That is the whole idea behind the masks in the next section.
Masks and flags
One bit per option is the cheapest way to store a set of switches. |= sets a bit, &= ~ clears it, ^= toggles it, and & against the same mask tests it. Each flag is a named constant, which is the style rule from lesson 4.
#include <stdio.h>
#define FLAG_READ (1u << 0)
#define FLAG_WRITE (1u << 1)
#define FLAG_EXEC (1u << 2)
static void show(const char *label, unsigned int flags)
{
printf("%-12s %u%u%u\n", label,
(flags & FLAG_EXEC) ? 1u : 0u,
(flags & FLAG_WRITE) ? 1u : 0u,
(flags & FLAG_READ) ? 1u : 0u);
}
int main(void)
{
unsigned int flags = FLAG_READ;
show("read", flags);
flags |= FLAG_WRITE;
show("read+write", flags);
flags &= ~FLAG_READ;
show("write", flags);
flags ^= FLAG_EXEC;
show("write+exec", flags);
printf("read set? %d\n", (flags & FLAG_READ) != 0);
return 0;
}
gcc -Wall -Wextra flags.c -o flags
./flags
read 001
read+write 011
write 010
write+exec 110
read set? 0
The display prints exec, write and read in that order to match the bit numbering, not the order the flags were defined in. Clearing a bit with flags &= ~FLAG_READ keeps every other bit, which is why the complement is applied to the mask and not to the flags.
Extracting fields
A packed colour is three bytes in one integer. Shifting moves the field of interest into the low bits and the mask removes the neighbours. The reverse operation shifts back and ORs the pieces together, and the result equals the original value.
#include <stdio.h>
int main(void)
{
unsigned int colour = 0x4A7FB2u;
unsigned int red = (colour >> 16) & 0xFFu;
unsigned int green = (colour >> 8) & 0xFFu;
unsigned int blue = colour & 0xFFu;
printf("#%06X\n", colour);
printf("red %3u\n", red);
printf("green %3u\n", green);
printf("blue %3u\n", blue);
printf("repacked 0x%06X\n", (red << 16) | (green << 8) | blue);
return 0;
}
gcc -Wall -Wextra fields.c -o fields
./fields
#4A7FB2
red 74
green 127
blue 178
repacked 0x4A7FB2
0xFF is eight set bits, so the mask keeps exactly one byte. A mask one bit too wide would pull part of the next field into the result, and the value would still look plausible.
Counting set bits
A loop that shifts the value right and adds the low bit is the portable way to count ones; it runs once per bit. GCC also provides __builtin_popcount, which compiles to a single instruction when the processor has one. The two must agree.
#include <stdio.h>
int main(void)
{
unsigned int value = 0xB6u;
int count = 0;
for (unsigned int bits = value; bits != 0; bits >>= 1) {
count += (int) (bits & 1u);
}
printf("set bits: %d\n", count);
printf("builtin: %d\n", __builtin_popcount(value));
printf("width: %d\n", __builtin_popcount(0u));
return 0;
}
gcc -Wall -Wextra popcount.c -o popcount
./popcount
set bits: 5
builtin: 5
width: 0
__builtin_popcount is a GCC extension, not part of the C library; a program that must build with another compiler keeps the loop, or uses the C23 header stdbit.h which the course covers in the part on modern C.
Shift counts
Two shifts are wrong in the same file: one asks for a shift by the width of the type, the other moves a set bit into the sign bit of a signed int. Both are undefined, and GCC reports both when the second warning level is enabled.
#include <stdio.h>
int main(void)
{
unsigned int value = 1u << 32;
int shifted = 1 << 31;
printf("%u %d\n", value, shifted);
return 0;
}
gcc -Wall -Wextra -Wshift-overflow=2 badshift.c -o badshift
badshift.c: In function 'main':
badshift.c:5:29: warning: left shift count >= width of type [-Wshift-count-overflow]
5 | unsigned int value = 1u << 32;
| ^~
badshift.c:6:21: warning: result of '1 << 31' requires 33 bits to represent, but 'int' only has 32 bits [-Wshift-overflow=]
6 | int shifted = 1 << 31;
| ^~
A shift count must be between zero and one less than the width of the promoted left operand. To set the top bit of a signed type, start from 1u and store the result in an unsigned type, or use the appropriate fixed-width type from lesson 6.
Exercises
- Print an unsigned byte as eight bits without a loop, using one printf and shifts inside the argument list.
- Rotate a 32-bit value left by n bits with a loop and shifts, and test it with n = 0, 4 and 32.
- Pack a date into one 32-bit integer as year, month and day fields, then unpack and print it. Choose the field widths and document them.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
How many bits does one hexadecimal digit represent?
Answer
4
Each hex digit stands for four bits, so two digits spell one byte exactly.
-
What does
x << ndo to an unsigned value when no set bit is shifted out?Answer
Multiplies it by 2 to the power n
A left shift moves every bit toward the high end, which multiplies the value by a power of two.
-
What fills the vacated high bits when an unsigned value is shifted right?
Answer
Zeros
A right shift of an unsigned type fills with zeros; a signed negative value has an implementation-defined fill.
-
What does
flags &= ~FLAG_READdo?Answer
Clears the read bit and keeps the others
The complement has every bit set except the mask, so the AND clears that one bit and leaves the rest unchanged.
-
What does
0xA5u >> 4evaluate to?Answer
10
0xA5is 1010 0101, and shifting it right by four bits leaves the high nibble, which is 10. -
What does
0xA5u & 0x0Fevaluate to?Answer
5
The mask keeps the low four bits, which are 0101, or 5.
-
What does this program print?
#include <stdio.h> int main(void) { unsigned int flags = 1u << 0; flags |= 1u << 1; printf("%u\n", flags); return 0; }Answer
3
Read is bit 0 and write is bit 1, so setting both gives the value 3.
-
What does
__builtin_popcount(0xB6u)return?Answer
5
0xB6is 1011 0110, which has five set bits. -
This program is built with
gcc -std=c17 -Wall -Wextra -Wshift-overflow=2 badshift.c -o badshift. What does GCC warn about?#include <stdio.h> int main(void) { unsigned int value = 1u << 32; printf("%u\n", value); return 0; }Answer
left shift count >= width of type [-Wshift-count-overflow]
A shift count must be less than the width of the promoted operand; 32 is not, so the shift is undefined.
-
This program is built with
gcc -std=c17 -Wall -Wextra -Wshift-overflow=2 badover.c -o badover. Which warning flag does GCC print?#include <stdio.h> int main(void) { int shifted = 1 << 31; printf("%d\n", shifted); return 0; }Answer
-Wshift-overflow=
The signed result of
1 << 31does not fit, and the warning belongs to-Wshift-overflow=.
The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev
