Realistic task for teaching bit operations

Question

I'm looking for a function or algorithm that requires extensive bit manipulation, but is not complicated in its nature and purpose, so that students remain focused on bit operations.

Now I use Win32 API GetVersion(): it returns system version components encoded in a 32-bit integer. Although deprecated, it's a comprehensive real-world example that requires masking, shifts, and bit testing. Students also learn to figure out needed operations from documentation.

However, I'd like to move away from MS-Windows. What an equivalent facility might be? It may even be an external library, if it's free and easy to plug in (we already use libcurl).

The language is C++. Students are 1st year, not pure CS (industrial automation).

Answer 1

varints

Implement encoding and decoding something like Protobuf's varint, perhaps without using negative numbers. Quoting:

Each byte in a varint, except the last byte, has the most significant bit (msb) set – this indicates that there are further bytes to come. The lower 7 bits of each byte are used to store the two's complement representation of the number in groups of 7 bits, least significant group first.

So to decode you need to go through a byte string and:

1. Take the 7 LSBs
2. Shift those 7 LSBs into the output variable
3. Check the MSB and continue or break

GPIO/hardware

Also, as mentioned in comments, hardware does usually require bit manipulation when writing drivers to interface with control registers (I have seen the reply stating it's not viable, just mention this for completeness). This is most prominent in GPIOs, where you can for example have one 32 bit register splits as 16 two-bit fields, one per GPIO.

BCD

Just remembered, there's another use case very common in electronics which you actually can do with pure software: Binary-coded decimal. The simplest version, which Wikipedia calls Natural BCD encodes two decimal digits as two separate 4-bit values in a single byte. This type of coding was used with 7-segment displays and to this very day is quite common in real-time clock ICs.

Answer 2

Maybe a bit too complicated, but fun nevertheless: Teach them about bitboards.

Conveniently enough, a chess-board has precisely 64 squares, so a 64-bit integer can store one bit of boolean information per square. Now the whole state of the board (disregarding en-passant and castling for now) can be encoded by having one integer per type of figure and one integer for all white figures.

• Want to find the white pawns? use pawn & white.

• The black pawns? pawn & !white

• Want to find all occupied squares? all = pawn | rook | knight | bishop | king | queen

• Squares reachable by white pawns in a normal move? (pawn & white) << 8 & !all

• In a two square move? (((pawn & white & 0xff00) << 8 ) & (!all) ) << 8) & !all

The possibilities range from trivial to requiring detailed understanding of bit-operations and they are indeed used by real chess engines. If you provide a bit of code to visualize the results, these might also be fun to simply toy around with.

Answer 3

Possibly prior to Buffy's wonderful answer, if the goal is to help students gain practice and fluency with the basic operations:

1. Addition and subtraction without using + and -.
2. Multiplication by 2s and integer division by the same.
3. The Russian Peasant algorithm for more general multiplication.
4. A string comparison that ignores case (presumably using ascii)
5. If you provide a 7-segment display, they can encode BCD onto the 7-segment display.
6. And finally, in the spirit of "give a man a fire, and he'll be warm for the night, but set a man on fire and he'll be warm for a lifetime" you can have them learn to swap numbers in place without a temporary variable.

Answer 4

One of my first (Fortran) programs was one to use bit masks to find all prime numbers less than some large number. I my case the maximum was twice the number of bits in the memory locations available to a user program, but a refinement can bypass that by stating a start point.

The idea is that in a large array, every bit of every word represents an odd number. A mask is a word that has bits set corresponding to multiples of some prime and a set of masks repeats the sequence of multiples until it repeats. So a set of masks for 17 has every 17th bit set.

The set of masks is then applied (bit operations) to the large array of "odds", leaving only those that are not multiples of that prime. Repeat for the next prime. Create the "mask list" and then apply it to the array.

The masks are easier to create than it seems and the whole operation is very fast. I'll let you think about which bit operations should be used.

The result is an array consisting of words with only prime number equivalent bits set, which can then be read out for the actual values.

The actual execution of this on old (IBM 1130) hardware was pretty dramatic since it is so compute and memory intensive. It was obvious to operators running the machine when my program was executing by just looking at the lights on the front panel of the machine. You will miss that experience, sadly.

If you are really innovative, note that it can probably be parallelized.

Answer 5

Here's a few ideas for things that a student might conceivably end up working with. Some of these are a bit more advanced than your basic example of decoding a byte-packed list of numbers from an API. The more advanced ones are also somewhat skewed towards cryptography, both because it's a field I'm familiar with and because cryptographic algorithms tend to make heavy use of bit manipulation.

• As a simple basic exercise, why not just implement a basic bitset-like class? Start with a fixed number of, say, 32 or 64 bits (so that they can be comfortably stored in a single integer) and just provide operations for setting, clearing and testing individual bits. Then move on to more complex set operations like taking the union or intersection of two bitsets and testing whether two bitsets have any set bits in common or whether one bitset is a subset of another. And finally extend the class to allow an arbitrary number of bits.

• Implement a Bloom filter. The bit operations needed are similar to Buffy's prime number sieve example, i.e. setting and examining individual bits in an array (and could be easily implemented using the bitset class from the first exercise above, if you choose to start with it), but unlike finding (relatively small) prime numbers, Bloom filters are actually useful as more than just a learning exercise.

• Implement a linear feedback shift register, and use it to calculate a cyclic redundancy checksum. CRCs are everywhere in industry, and knowing how they work is certainly useful. And LFSRs have plenty of other uses as well.

• As an extension of the above, implement a stream cipher based on a non-linear feedback shift register. One possibly interesting advanced exercise, off the top of my head, could be to give the students a naïve (one bit per iteration) reference implementation of Trivium and ask them to make it faster. (The algorithm is designed so that up to 64 bits can be generated per iteration by using bitwise operations on 64-bit words.)

• Introduce your students to Galois fields and have them implement arithmetic operations in GF(2ⁿ) for some number of bits n. Addition is trivial — it's just bitwise XOR. For multiplication, you have a bunch of options: carryless multiply and then reduce, Russian peasant multiplication, multiplication via discrete logarithms, etc. You may also want to compute the multiplicative inverse; this can be done using a variant of Euclid's algorithm, or again via discrete logarithms.

• Once you have an implementation of the multiplicative inverse in GF(2⁸), use it to implement the AES S-box, and then actual AES encryption. As a learning exercise, I'd suggest splitting this into multiple parts: first implement each of the component operations (SubBytes, ShiftRows and MixColumns; each features different kinds of bit manipulation) independently, then combine them into the full round function (together with AddRoundKey, which is just a bitwise XOR), then implement the key schedule and finally put it all together. (You may also want to have a brief side discussion of why each of the components is necessary.)

• As an alternative to all this crypto stuff, implement an interpreter for some simple bytecode or assembly-like language, such as (a subset of) the "Redcode" language used in Core War. While this can be done using few if any bit operations using a naïve representation of the instructions, for efficiency (and pedagogy) it's a good idea to pack the opcode, modifiers and addressing modes of each instruction into a single integer. (16 bits will just suffice for ICWS'94 Redcode, if you leave out the LDP and STP instructions.) Decoding this then provides a nice example of practical bit manipulation, somewhat similar to your Windows version number decoding example.

Also, in general, as soon as your students have a bit of familiarity with bit manipulation, I'd suggest going through some lists of bit twiddling hacks and introducing your students to some useful tricks that can be done with just a few bit operations, such as:

• calculating the remainder modulo a power of 2,
• checking whether an integer is a power of 2, or
• counting the number of 1 bits in an integer.

(The last one might also be useful as part of the bitset exercise, for implementing a set size operation.)

Answer 6

Reading and editing the files created by Minecraft requires a fair bit of bit manipulation, and would likely grab the attention of at least some of your students. The bittiest part is that, for a chunk with K different kinds of blocks, the blocks themselves are stored as a dense array of log(K) bit numbers. The Minecraft wiki has an excellent description of the file format, which is another advantage of this task- good documentation makes for fast learning.

https://minecraft.gamepedia.com/Chunk_format

Answer 7

One I've used is an algorithm which solves Latin squares (the algorithm is easy to extend to Sudoku puzzles). When solving by hand, it's common to keep track of which digits are possible in each cell. Bitmasks can be used analogously in an algorithm, so for example if 1, 3 and 4 are the possible digits in some cell then 0b0000011010 represents this set of possibilities (the bits are numbered from least significant to most significant, and the 0th bit is unused because the digit 0 is unused).

The students then need to write a few methods to manipulate bitmasks, which will simplify the writing of the rest of the algorithm:

• Test if a digit is possible: (mask & (1 << digit)) != 0
• Remove a digit from a set of possibilities: mask &= ~(1 << digit)
• Initialise a set of possibilities so all n digits are allowed: ((1 << n) - 1) << 1
• Count how many digits are possible: various ways to do this using bitwise operations in a loop.
• Get the smallest possible digit from a set of possibilities: various ways.

The | and ^ operations can also be motivated by wanting to add or toggle a digit as a possibility; in my case, the solver algorithm did not require doing either.

Answer 8

Two assignments that I have used are:

1. a library for setting/getting bit fields from an integer value.
2. performing floating point addition/subtraction without using floating point types.

The library may be used in the second assignment. Alternatively, the second assignment can be completely standalone. The assignments are in C and are for a course in computer organization. Part of this course involves the LC3 assembly language, so the concept of bit fields comes into play when extracting the opcode and operands from the instruction. This is done when they write a simulator for the LC3 computer. Sometimes the students write an assembler and thus need to produce a "binary" value from the opcode and operands.

Both assignments assume that the student has had an introduction to binary/hex numbers. I would be happy to supply all the source materials.

https://www.cs.colostate.edu/~fsieker/CurrentSemester/assignments/FIELD/doc

https://www.cs.colostate.edu/~fsieker/CurrentSemester/assignments/FLOAT.C/doc

Answer 9

How about graphics?

Start out simple with requiring them to do things like "make a bitmask that starts at bit 7 and ends at bit 12".

Use a single-bit image format. Display the results on the screen in black and white.

Now have 3 bitmasks, one for each of RGB. The library takes the 3 bitmasks and combines them to display it on the screen.

Now they have to find the mask for the combined colors -- the ones that have RG (yellow), GB (aqua), RB (fuchsia), and RGB (white) turned on.

Now we change the compositing rule. Things that have any two channels produce the third. Things that have one channel twice produce black.

You can keep doing more stuff. Shift one the channels 1, or X, pixels left or right. Stretch one of the channels by a factor of 2, 3, an integer. Stretch a channel by a rational factor.

Apply a texture; given a mask-channel, apply it to a set of other channels that represent a color texture you want to see in that mask-channel.

Punch through. Given a mask-channel, produce a hole in a set of other channels.

Horizontal squeeze by 2, 4, 8 16; given a scanline, count how many bits are in each run. Library displays the result (with anti-aliasing!)

Vertical squeeze. Shuffle two scanlines together so you can feed it to horizontal squeeze and get a vertical one.

Zoom out. Do a 4x vertical and 4x horizontal squeeze to get a 4x zoom out.

This can go even further; the occlusion based painting algorithm uses bit operations in place of the usual alpha calculations. (a 4x4 mask can be represented as a 16 bit value; instead of (both premultiplied color) A' = A0*(1-A1) + A1 and C' = C0*(1-A1) + C1 we get A' = A1|A0 and C' = C1 + BitCount(A0&~A1)*C0/16, for example.)

But the point is, you can (with a library) turn their bit operation work into visible graphics effects, with the students not having to know anything about how the graphics part works.

If you write the library well, they can also get to play with fun and strange visual effects.

---

using mutable_scanline = std::span<uint32_t>;
using scanline = std::span<const uint32_t>;

ScanlineDrawing create_drawing();
// 1 bit per pixel
void ScanlineDrawing::draw_bw( scanline );
// 1 bit per channel, 3 bits per pixel
void ScanlineDrawing::draw_rgb3( scanline );
// values only go up to 2^(bits_per_pixel-1).
void ScanlineDrawing::draw_greyscale( scanline, int bits_per_pixel );
void ScanlineDrawing::draw_rgb_x( scanline, int bits_per_pixel );

void ScanlineDrawing::display();

there is our basic library.

We also get a test harness that provides you with scanlines to process.

Functions to write:

void fill( mutable_scanline, int start, int length );

// take 3 bw channels and make a single rgb3 one.
std::vector<uint32_t> make_rgb3( scanline, scanline, scanline );

// Overwrites [start, start+length) bits in dst with bits from src.
// all bits must be within dst's range, or no guarantees
void blit( scanline src, mutable_scanline dst, int start, int length );

// moves values amount right (or left if negative).
// Fills blanks with 0s.
void shift( mutable_scanline, int amount );

// moves values amount right (or left if negative).  Stuff falling off
// edge shows up on other side
void rotate( mutable_scanline, int amount );

// scale the scanline down.  Tail should be 0s
void scale_by_2( mutable_scanline );

// scale the scanline down.  Tail should be 0s
void scale_by_4( mutable_scanline );

// scale the scanline down.  Tail should be 0s
void scale_by_16( mutable_scanline );

// take any number of channels, and interlace them 1 bit at a time
std::vector<uint32_t> interlace( std::span<const scanline> );

// take any number of channels, and interlace them width bits at a time
std::vector<uint32_t> interlace( std::span<const scanline>, int width );

build some test harnesses to use the above and they'll be able to do most of what I described above.

Calls fill (which students write)

void make_square( std::span<mutable_scanline>, int x, int y, int size );

Calls shift or rotate:

void do_pan( std::span<mutable_scanline>, int dx, int dy, bool bWrap=false );

Copies src multiple times over dst -- calls blit and shift.

void tile( std::span<scanline const> src, std::span<mutable_scanline> dst, int offsetx, int offsety );

Instead, calls blit and rotate:

void tile2( std::span<scanline const> src, std::span<mutable_scanline> dst, int offsetx, int offsety );

// zooms by a factor of 2 or 4. Uses interlace(scan, width) and scale_by_4 or scale_by_16.

void zoom_x2( std::span<mutable_scanline> )
void zoom_x4( std::span<mutable_scanline> )

Here we have relatively simple tasks in a real framework that does real things on the real screen.

You expose the new programmer to "real programs" they can read over, and mimic the style of.

You can have bonus assignments like "make a pretty drawing using a custom-written function".

You can convert real pictures into this format; the anti-aliasing zoom trick lets you get up to 4 bits of color in each channel, which is enough to have a real color picture show up. The bit-operations applied to 15 bits per pixel channels still works, you just have to pan by multiples of 15 horizontally. So you could even get a successful program to generate a little animation. ;)

Answer 10

This is not a single function/algorithm, but emulator development heavily relies on bit manipulation. One interesting task for students could be to implement the opcode parsing for the Chip-8 . This means, provided a framework that implements the device abstraction (memory, registers), sound, and graphics, the only remaining task is to parse the opcodes and write the correct data into the registers (which are represented by variables).

Here is a Github project of a Chip-8 emulator where the massive if/else branch handles each opcode. An opcode table can be found on wikipedia.

I think this is a great exercise, because most of the work is messing with bits and simply writing data into a variable (which represents a register). The task can be broken down into many small units (each opcode/groups of opcodes). After successful implementation, the students have a working emulator and can play pong or other games, which can be a very rewarding feeling. This task gives the students a first look at hardware architecture (what is a register, instruction pointer, and memory) without the complexity of modern CPUs. Lastly, the Chip-8 is very small and more advanced students can peek around the source code and with some guidance or documentation might be able to understand it fully.

A drawback is that there are many implementations on Github and it is easy to cheat and look it up. A bigger hurdle is that it requires quite a lot (depending on systems programming knowledge) of initial work from the teacher to implement the framework. As this is a graphics application, it might take some time until it works on every students computer if they use a mix of operating systems and versions.

Answer 11

What may be the very best algorithm for demonstrating the value of bit shifts is division! Everyone learning CS should have very solid intuitions around division, and trying to divide two numbers using only addition, subtraction, bit shifts and comparison is a wonderful demonstration of the power of bit shifting.

I would go through two steps (levels of enlightenment, if you will):

1. Division using repeated subtraction of the divisor from the dividend. Easy enough to understand, but gets inefficient with big numbers, as it scales with O(n)
2. Division using repeated subtraction of powers of two of the divisor from the dividend. Easy to show how it works (and why it's so efficient) by demonstrating counting by 2 divisors, and then 4 divisors, and then 8 divisors, and then generalizing to powers of two. Scales with O(log(n))

It's a great problem for 3 reasons:

• No explanation of the problem needed: Everyone already knows what division is, and has a solid understanding of how it works
• The inefficient, non-bit-shifty solution is easy: Most students should be able to figure out Step 1 above on their own given enough time. I would give them 5 minutes or so to think hoping someone in the room stumbles on it before introducing that solution
• There are multiple variants of the bit-shifty solution: For those who struggle to grasp the first variant of the bit-shifty solution, there are several alternatives that are fairly easy to recognize as mathematically equivalent, so try the above solution for everyone, and then try additional solutions for those few for whom the above doesn't click, and within a few minutes everyone is on the same page. If you can't see the solutions on LeetCode, look up division by two with bit shifting, there are several ways of making it work

Answer 12

Reading or writing a binary file usually involves bit operations. This is especially true for older formats created back when memory and disk were scarce and the authors were trying to minimise file size by packing as many values into a byte as possible.

Maybe set a project to write a pair of utilities to convert files between a common modern format and an older one that's fallen out of favour but still sees a fair amount of support despite not being as common as it once was. This would have the advantage of support in existing software to make it easy to both make test cases and to test the program outputs.

As an example, Creative Labs' VOC format supports several low-bit-depth sample formats (which definitely need bit operations to extract individual samples from) and was fairly common back in the days before Windows 95, but got displaced by WAV. Both formats support a variety of encodings and are reasonably well-documented.

If you've already covered audio through the use of some library, like SDL, or are planning to do so, you could have a project of making a playback program for another assignment.

And yes, I know someone else suggested reading Minecraft chunks, but I don't think that's a good fit as it's a bit too specialised a format. I think something more generic like audio or images would be a better fit, as it's fairly easy to see a need to include support for loading one of those files in a larger program.

Answer 13

Create a class that acts somewhat like an array of small numbers, but is, in fact, entirely encoded in an unsigned 32 bit number. Say, encode six numbers between 0 and 31 into 32 bits (aligning on an oddball bit-number (5 in this case) makes it likely that they will not find any samples on-line that they can copy directly).

They have to be able to set a value at an index, get a value at an index, and maybe enumerate the entire collection.

You could also randomly change the bit alignments in order to reduce copying (though I would skip 4, 8 and 16).