Has this word a repeated letter? Keep one switch per letter of the alphabet, and turn each on as its letter goes by. Watch the 26 switches fit in one integer.
Finding repeated letters with bits
The letters of parallel, one bit each
void repeats_by_bits(const char *s){ unsigned seen = 0; for (size_t i = 0; s[i] != '\0'; i++) { unsigned bit = 1u << (s[i] - 'a'); if (seen & bit) printf("%c again at %zu\n", s[i], i); seen |= bit; } printf("mask %#x\n", seen);}int main(void){ repeats_by_count("parallel"); repeats_by_bits("parallel"); bool x = anagrams("signal", "aligns"); bool y = anagrams("signal", "single"); printf("%d %d\n", x, y); return 0;}Now the same question with one unsigned int.
- seen
- 0
- in hex
- 0x0
Output
a appears 2 times l appears 3 times
Describe this picture
Two strips, with the code of repeats_by_bits and main beside them, the line about to run marked. Above, the eight letters of “parallel”. Below, the 26 bits of unsigned seen, as in a binary number: bit 25, labelled z, on the left, and bit 0, labelled a, on the right; all are 0 at first. The clip takes about 16 seconds. The marker i reads each letter in turn and the letter’s bit is tinted: p switches on bit 15, a bit 0, r bit 17. At i = 3 the second a finds bit 0 already on: the letter and the bit light in the warning tone, and the output adds a again at 3. l switches on bit 11, the next l, at 5, is a repeat, e switches on bit 4, and the last l, at 7, is a repeat again. The repeated letters stay in the warning tone. Last, the 26 bits are read as one number: the name under them reads “seen = 165905 = 0x28811”, and the output adds mask 0x28811. The readouts give seen in decimal and in hex at every step. The transport plays and pauses, steps one line back or forward, and scrubs; a paused step is kept in the page address as letter-bits.step.
One switch per letter
To find repeated letters, remember which letters have gone by. With lower-case letters only, as on this page, there are 26 possibilities, and c - 'a' turns a letter into its number: a is 0, b is 1, z is 25. That number can index a table of counts, or pick one bit of an integer.
A table can count how often each letter appears. A bit can only say whether a letter has appeared, but 26 bits fit in one unsigned int, so the whole set is one number.
The code and its cost
A count table
int count[26] = { 0 };
for (size_t i = 0; s[i] != '\0'; i++)
count[s[i] - 'a']++;For “parallel” the counts are a 2, e 1, l 3, p 1, r 1, and 0 for the other 21 letters; they add up to 8, the length. repeats_by_count then prints the letters counted more than once: a appears 2 times and l appears 3 times.
Bit operations
The bits of an unsigned hold a set of up to 32 small numbers. With 1u << k, the number with only bit k on:
| Operation | Code |
|---|---|
| set bit k | m |= 1u << k; |
| test bit k | m & (1u << k): nonzero if set |
| clear bit k | m &= ~(1u << k); |
&, | and ~ work on each bit separately. && and || work on whole truth values: 2 && 1 is 1, 2 & 1 is 0.
Repeats with a mask
void repeats_by_bits(const char *s)
{
unsigned seen = 0;
for (size_t i = 0; s[i] != '\0'; i++) {
unsigned bit = 1u << (s[i] - 'a');
if (seen & bit)
printf("%c again at %zu\n", s[i], i);
seen |= bit;
}
printf("mask %#x\n", seen);
}Each letter tests its bit, then sets it. For “parallel” the repeats are a at 3, l at 5 and l at 7. The mask ends with bits 15 (p), 0 (a), 17 (r), 11 (l) and 4 (e) on: 32,768 + 1 + 131,072 + 2,048 + 16 = 165,905, which %#x prints as 0x28811.
Anagrams
Two words are anagrams if they use the same letters the same number of times. A mask cannot tell: l once and l three times set the same bit. Counts can. anagrams adds 1 for each letter of the first word, subtracts 1 for each letter of the second, and checks that all 26 counts are back at 0. “signal” and “aligns” are anagrams; “signal” and “single” are not: a is left at 1 and e at −1. The program prints 1 0.
Every function here makes one pass over each string and at most one pass over the 26 letters.
Worked example
Three bit operations. Start with m = 11, binary 1011. Setting bit 2 gives 1111, 15. Testing bit 4: 11 & 16 = 0, not set. Clearing bit 0 of 11 gives 1010, 10.
Permission flags. File permissions give read 4, write 2 and run 1, one bit each. Read and run is 4 | 1 = 5. The owner allowed all three and everyone else read and run is 7, 5, 5, the familiar 755.
Counts by hand. “parallel”: a 2, e 1, l 3, p 1, r 1, total 8.
Two checks. What is the mask after “dsp”? (Bits 3, 18 and 15: 8 + 262,144 + 32,768 = 294,920.) Are “listen” and “silent” anagrams? (Yes.)
Where it’s used
Permission flags. File permissions and the options passed to system functions are bits combined with | and tested with &.
Bloom filters. A Bloom filter, Chapter 20, is a long array of bits that records “seen” for many items at once.
Sets of small numbers. Compilers, games and puzzle solvers keep sets of small integers as bits: union is |, intersection is &, and both take one instruction.
Reference card
| Code or idea | Meaning |
|---|---|
c - 'a' | a letter’s number, 0 to 25 |
count[c - 'a']++ | count a letter |
1u << k | only bit k on |
m |= 1u << k | set bit k |
m & (1u << k) | test bit k |
m &= ~(1u << k) | clear bit k |
& against && | bits against truth values |
| a mask | seen or not: cannot count |
| anagrams | equal count tables |
Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.