<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-01-29T05:37:54.590Z
2021-01-29T05:37:54.590Z
Rohan
<p>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).</p>
<p>They have to be able to set a value at an index, get a value at an index, and maybe enumerate the entire collection.</p>
<p>You could also randomly change the bit alignments in order to reduce copying (though I would skip 4, 8 and 16).</p>

CC BY-SA 4.0
2021-01-12T00:33:29.547Z
2021-01-12T00:33:29.547Z
Flydog57
<p><strong>varints</strong></p>
<p>Implement encoding and decoding something like <a href="https://developers.google.com/protocol-buffers/docs/encoding#varints" rel="nofollow noreferrer">Protobuf's varint</a>, perhaps without using negative numbers. Quoting:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>So to decode you need to go through a byte string and:</p>
<ol>
<li>Take the 7 LSBs</li>
<li>Shift those 7 LSBs into the output variable</li>
<li>Check the MSB and continue or break</li>
</ol>
<p><strong>GPIO/hardware</strong></p>
<p>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.</p>
<p><strong>BCD</strong></p>
<p>Just remembered, there's another use case <em>very</em> common in electronics which you actually <em>can</em> do with pure software: <a href="https://en.wikipedia.org/wiki/Binary-coded_decimal" rel="nofollow noreferrer">Binary-coded decimal</a>. The simplest version, which Wikipedia calls <em>Natural BCD</em> 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.</p>

CC BY-SA 4.0
2021-01-11T20:35:07.913Z
2021-01-12T01:26:05.607Z
2021-01-12T01:26:05.607Z
jaskij
<p>Maybe a bit too complicated, but fun nevertheless: Teach them about <a href="https://en.wikipedia.org/wiki/Bitboard" rel="noreferrer">bitboards</a>.</p>
<p>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.</p>
<ul>
<li><p>Want to find the white pawns? use <code>pawn &amp; white</code>.</p>
</li>
<li><p>The black pawns? <code>pawn &amp; !white</code></p>
</li>
<li><p>Want to find all occupied squares? <code>all = pawn | rook | knight | bishop | king | queen</code></p>
</li>
<li><p>Squares reachable by white pawns in a normal move? <code>(pawn &amp; white) &lt;&lt; 8 &amp; !all</code></p>
</li>
<li><p>In a two square move? <code>(((pawn &amp; white &amp; 0xff00) &lt;&lt; 8 ) &amp; (!all) ) &lt;&lt; 8) &amp; !all</code></p>
</li>
</ul>
<p>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.</p>

CC BY-SA 4.0
2021-01-11T14:09:35.717Z
And you just gave me an afternoon self-study idea :D
mishan
CC BY-SA 4.0
2021-01-11T17:31:29.577Z
It would take one more 64-bit integer to keep track of the en-passant states of the pawns (just use `1` on any space that contains a pawn that has done it), and since the rules of promotion REQUIRE that pawns promote when they reach the end of the board, the two end rows can safely be used to store information about whether that team has castled.  So, I believe that means you can store a full game state in 8 64-bit ints, with 14 bits of information left over in those two castling rows.  6 for the piece types, one for color, and one for en-passant and castling.  Neat!!
Ben I.
CC BY-SA 4.0
2021-01-11T18:22:27.967Z
@BenI: See also [Smallest chess board compression](https://codegolf.stackexchange.com/questions/19397/smallest-chess-board-compression) challenge on [codegolf.se].
Ilmari Karonen
CC BY-SA 4.0
2021-01-11T22:52:04.640Z
Truly excellent and interesting answer. Thanks.
Eric Duminil
CC BY-SA 4.0
2021-03-29T21:58:22.140Z
You can use bitboards for tic-tac-toe and simpler games if chess is out of scope.
ggorlen
CC BY-SA 4.0
2021-01-11T13:28:02.430Z
2021-01-11T13:28:02.430Z
mlk
<p>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.</p>
<p>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.</p>
<p>The set of masks is then applied (bit operations) to the large array of &quot;odds&quot;, leaving only those that are not multiples of that prime. Repeat for the next prime. Create the &quot;mask list&quot; and then apply it to the array.</p>
<p>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.</p>
<p>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.</p>
<p>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.</p>
<p>If you are really innovative, note that it can probably be parallelized.</p>

CC BY-SA 4.0
2021-01-10T14:03:59.807Z
Large bitmap as an integer set representation is a good choice, there are even more applied tasks it's used for. STEM students are familiar with the sieve of Eratosthenes, however, searching for prime numbers won't look very practical to them.
PlushBeaver
CC BY-SA 4.0
2021-01-11T09:01:50.797Z
@PlushBeaver Both PostgreSQL and Elasticsearch combine index search results by mapping documents/rows to bits in a bitmap and then combining them using bit operations on them. Maybe that's more practical.
AndreKR
CC BY-SA 4.0
2021-01-10T13:25:07.890Z
2021-01-10T13:25:07.890Z
Buffy
<p>Possibly prior to Buffy's wonderful answer, if the goal is to help students gain practice and fluency with the basic operations:</p>
<ol>
<li>Addition and subtraction without using <code>+</code> and <code>-</code>.</li>
<li>Multiplication by 2s and integer division by the same.</li>
<li>The Russian Peasant algorithm for more general multiplication.</li>
<li>A string comparison that ignores case (presumably using ascii)</li>
<li>If you provide a 7-segment display, they can encode BCD onto the 7-segment display.</li>
<li>And finally, in the spirit of &quot;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&quot; you can have them learn to swap numbers in place without a temporary variable.</li>
</ol>

CC BY-SA 4.0
2021-01-10T16:44:20.773Z
I should note that the [IBM 7030 Supercomputer](https://en.wikipedia.org/wiki/IBM_7030_Stretch) and their first transistorized computer, didn't have an "adder". It used table lookup to provide addition. It's nickname inside IBM was CADET (Can't Add, Doesn't Even Try). I knew the guy that gave it this name.
Buffy
CC BY-SA 4.0
2021-01-10T16:48:27.173Z
Some engineers came to my colleague (hallway conversation) and said that they were having trouble designing an adder (remember, this was long ago) and that the result would be overly expensive - a substantial fraction of the cost. Bill suggested table lookup from which the nickname arose.
Buffy
CC BY-SA 4.0
2021-01-10T16:51:30.877Z
@Buffy That is an amazing story!
Ben I.
CC BY-SA 4.0
2021-01-10T17:01:10.440Z
Hmmm. I'm getting CADET hits for the [1620](https://en.wikipedia.org/wiki/IBM_1620) instead. Perhaps I remember it wrong. Sneaky synapses.
Buffy
CC BY-SA 4.0
2021-01-10T20:05:54.147Z
If you can do subtraction with only bit operations (yes, you can) then you can do square roots with only bit operations.
Buffy
CC BY-SA 4.0
2021-01-11T17:10:34.487Z
I quite like number 1 here (and subsequently number 2). When I was first learning to do bitwise operations, I wasn't really sure what a practical application for them was, but I did find that this was a very fun thing to learn. It's also not overly complicated and can easily be solved on paper and implemented accordingly.
Will Eccles
CC BY-SA 4.0
2021-01-11T19:38:02.497Z
After you mentioned case-insensitive string comparison, I started thinking about UTF-8 and varint encoding/decoding. Typically it's library stuff, but used almost everywhere.
PlushBeaver
CC BY-SA 4.0
2021-01-12T00:20:04.303Z
The IBM 7030 Stretch had two arithmetic units with multiple carry-propagate adders and carry-save adders. (@Buffy, you're thinking of the IBM 1620 which used table lookup.) The 7030's adders are described in http://www.bitsavers.org/pdf/ibm/7030/Bloch_EngrDesOfStretch_1959.pdf
Ken Shirriff
CC BY-SA 4.0
2021-01-12T19:48:52.330Z
@Buffy I have a vague memory of an ancient book of "programming problems/exercises for the 1620" which included overwriting the arithmetic tables to work in different number bases.
alephzero
CC BY-SA 4.0
2021-01-10T15:10:19.727Z
2021-01-10T15:10:19.727Z
Ben I.
<p>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.</p>
<p><a href="https://minecraft.gamepedia.com/Chunk_format" rel="nofollow noreferrer">https://minecraft.gamepedia.com/Chunk_format</a></p>

CC BY-SA 4.0
2021-01-12T21:17:45.540Z
2021-01-12T21:17:45.540Z
QuadmasterXLII
<p>One I've used is an algorithm which solves <a href="https://en.wikipedia.org/wiki/Latin_square" rel="nofollow noreferrer">Latin squares</a> (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 <code>0b0000011010</code> 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).</p>
<p>The students then need to write a few methods to manipulate bitmasks, which will simplify the writing of the rest of the algorithm:</p>
<ul>
<li>Test if a digit is possible: <code>(mask &amp; (1 &lt;&lt; digit)) != 0</code></li>
<li>Remove a digit from a set of possibilities: <code>mask &amp;= ~(1 &lt;&lt; digit)</code></li>
<li>Initialise a set of possibilities so all <code>n</code> digits are allowed: <code>((1 &lt;&lt; n) - 1) &lt;&lt; 1</code></li>
<li>Count how many digits are possible: various ways to do this using bitwise operations in a loop.</li>
<li>Get the smallest possible digit from a set of possibilities: various ways.</li>
</ul>
<p>The <code>|</code> and <code>^</code> 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.</p>

CC BY-SA 4.0
2021-01-11T02:48:51.197Z
2021-01-11T02:48:51.197Z
kaya3
<p>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.</p>
<ul>
<li><p>As a simple basic exercise, why not just implement <strong>a basic <a href="http://www.cplusplus.com/reference/bitset/bitset/" rel="nofollow noreferrer">bitset</a>-like class</strong>?  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.</p>
</li>
<li><p>Implement a <a href="https://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow noreferrer"><strong>Bloom filter</strong></a>.  The bit operations needed are similar to <a href="https://cseducators.stackexchange.com/a/6731">Buffy's prime number sieve example</a>, 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.</p>
</li>
<li><p>Implement a <a href="https://en.wikipedia.org/wiki/Linear-feedback_shift_register" rel="nofollow noreferrer"><strong>linear feedback shift register</strong></a>, and use it to <a href="https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks" rel="nofollow noreferrer">calculate a cyclic redundancy checksum</a>.  CRCs are everywhere in industry, and knowing how they work is certainly useful.  And LFSRs have plenty of <a href="https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Applications" rel="nofollow noreferrer">other uses</a> as well.</p>
</li>
<li><p>As an extension of the above, implement a <a href="https://en.wikipedia.org/wiki/Stream_cipher" rel="nofollow noreferrer"><strong>stream cipher</strong></a> based on a <em>non</em>-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 <a href="https://en.wikipedia.org/wiki/Trivium_(cipher)" rel="nofollow noreferrer">Trivium</a> 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.)</p>
</li>
<li><p>Introduce your students to <a href="https://crypto.stackexchange.com/questions/2700/galois-fields-in-cryptography/2718#2718">Galois fields</a> and have them implement <a href="https://en.wikipedia.org/wiki/Finite_field_arithmetic" rel="nofollow noreferrer"><strong>arithmetic operations in GF(2<sup><em>n</em></sup>)</strong></a> for some number of bits <em>n</em>.  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 <a href="https://crypto.stackexchange.com/questions/12956/multiplicative-inverse-in-operatornamegf28/12962#12962">compute the multiplicative inverse</a>; this can be done using a variant of Euclid's algorithm, or again via discrete logarithms.</p>
</li>
<li><p>Once you have an implementation of the multiplicative inverse in GF(2<sup>8</sup>), use it to implement the <a href="https://en.wikipedia.org/wiki/Rijndael_S-box" rel="nofollow noreferrer">AES S-box</a>, and then actual <a href="https://en.wikipedia.org/wiki/Advanced_Encryption_Standard" rel="nofollow noreferrer"><strong>AES encryption</strong></a>.  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 <a href="https://en.wikipedia.org/wiki/AES_key_schedule" rel="nofollow noreferrer">key schedule</a> and finally put it all together.  (You may also want to have a brief side discussion of <a href="https://crypto.stackexchange.com/questions/20228/consequences-of-aes-without-any-one-of-its-operations">why each of the components is necessary</a>.)</p>
</li>
<li><p>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 &quot;<a href="http://vyznev.net/corewar/guide.html" rel="nofollow noreferrer">Redcode</a>&quot; language used in <a href="https://en.wikipedia.org/wiki/Core_War" rel="nofollow noreferrer"><strong>Core War</strong></a>.  While this <em>can</em> 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.</p>
</li>
</ul>
<p>Also, in general, as soon as your students have a bit of familiarity with bit manipulation, I'd suggest going through some lists of <a href="https://graphics.stanford.edu/%7Eseander/bithacks.html" rel="nofollow noreferrer"><strong>bit twiddling hacks</strong></a> and introducing your students to some useful tricks that can be done with just a few bit operations, such as:</p>
<ul>
<li><a href="https://graphics.stanford.edu/%7Eseander/bithacks.html#ModulusDivisionEasy" rel="nofollow noreferrer">calculating the remainder modulo a power of 2</a>,</li>
<li><a href="https://graphics.stanford.edu/%7Eseander/bithacks.html#DetermineIfPowerOf2" rel="nofollow noreferrer">checking whether an integer is a power of 2</a>, or</li>
<li><a href="https://stackoverflow.com/questions/22081738/how-does-this-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer-work">counting the number of 1 bits in an integer</a>.</li>
</ul>
<p>(The last one might also be useful as part of the bitset exercise, for implementing a set size operation.)</p>

CC BY-SA 4.0
2021-01-11T18:19:15.533Z
2021-01-11T18:19:15.533Z
Ilmari Karonen
<p>Two assignments that I have used are:</p>
<ol>
<li>a library for setting/getting bit fields from an integer value.</li>
<li>performing floating point addition/subtraction without using floating point types.</li>
</ol>
<p>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 &quot;binary&quot; value from the opcode and operands.</p>
<p>Both assignments assume that the student has had an introduction to binary/hex numbers. I would be happy to supply all the source materials.</p>
<p><a href="https://www.cs.colostate.edu/%7Efsieker/CurrentSemester/assignments/FIELD/doc" rel="nofollow noreferrer">https://www.cs.colostate.edu/~fsieker/CurrentSemester/assignments/FIELD/doc</a></p>
<p><a href="https://www.cs.colostate.edu/%7Efsieker/CurrentSemester/assignments/FLOAT.C/doc" rel="nofollow noreferrer">https://www.cs.colostate.edu/~fsieker/CurrentSemester/assignments/FLOAT.C/doc</a></p>

CC BY-SA 4.0
2021-01-10T16:38:11.867Z
2021-01-10T16:38:11.867Z
Fritz Sieker
<p>How about graphics?</p>
<p>Start out simple with requiring them to do things like &quot;make a bitmask that starts at bit 7 and ends at bit 12&quot;.</p>
<p>Use a single-bit image format.  Display the results on the screen in black and white.</p>
<p>Now have 3 bitmasks, one for each of RGB.  The library takes the 3 bitmasks and combines them to display it on the screen.</p>
<p>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.</p>
<p>Now we change the compositing rule.  Things that have any two channels produce the third.  Things that have one channel twice produce black.</p>
<p>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.</p>
<p>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.</p>
<p>Punch through.  Given a mask-channel, produce a hole in a set of other channels.</p>
<p>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!)</p>
<p>Vertical squeeze.  Shuffle two scanlines together so you can feed it to horizontal squeeze and get a vertical one.</p>
<p>Zoom out.  Do a 4x vertical and 4x horizontal squeeze to get a 4x zoom out.</p>
<p>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) <code>A' = A0*(1-A1) + A1</code> and <code>C' = C0*(1-A1) + C1</code> we get <code>A' = A1|A0</code> and <code>C' = C1 + BitCount(A0&amp;~A1)*C0/16</code>, for example.)</p>
<p>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.</p>
<p>If you write the library well, they can also get to play with fun and strange visual effects.</p>
<hr />
<pre><code>using mutable_scanline = std::span&lt;uint32_t&gt;;
using scanline = std::span&lt;const uint32_t&gt;;

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();
</code></pre>
<p>there is our basic library.</p>
<p>We also get a test harness that provides you with scanlines to process.</p>
<p>Functions to write:</p>
<pre><code>void fill( mutable_scanline, int start, int length );

// take 3 bw channels and make a single rgb3 one.
std::vector&lt;uint32_t&gt; 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&lt;uint32_t&gt; interlace( std::span&lt;const scanline&gt; );

// take any number of channels, and interlace them width bits at a time
std::vector&lt;uint32_t&gt; interlace( std::span&lt;const scanline&gt;, int width );
</code></pre>
<p>build some test harnesses to use the above and they'll be able to do most of what I described above.</p>
<p>Calls <code>fill</code> (which students write)</p>
<pre><code>void make_square( std::span&lt;mutable_scanline&gt;, int x, int y, int size );
</code></pre>
<p>Calls shift or rotate:</p>
<pre><code>void do_pan( std::span&lt;mutable_scanline&gt;, int dx, int dy, bool bWrap=false );
</code></pre>
<p>Copies src multiple times over dst -- calls blit and shift.</p>
<pre><code>void tile( std::span&lt;scanline const&gt; src, std::span&lt;mutable_scanline&gt; dst, int offsetx, int offsety );
</code></pre>
<p>Instead, calls blit and rotate:</p>
<pre><code>void tile2( std::span&lt;scanline const&gt; src, std::span&lt;mutable_scanline&gt; dst, int offsetx, int offsety );
</code></pre>
<p>// zooms by a factor of 2 or 4.  Uses <code>interlace(scan, width)</code> and <code>scale_by_4</code> or <code>scale_by_16</code>.</p>
<pre><code>void zoom_x2( std::span&lt;mutable_scanline&gt; )
void zoom_x4( std::span&lt;mutable_scanline&gt; )
</code></pre>
<p>Here we have relatively simple tasks in a real framework that does real things on the real screen.</p>
<p>You expose the new programmer to &quot;real programs&quot; they can read over, and mimic the style of.</p>
<p>You can have bonus assignments like &quot;make a pretty drawing using a custom-written function&quot;.</p>
<p>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.  ;)</p>

CC BY-SA 4.0
2021-01-11T15:24:27.910Z
2021-01-11T19:54:12.817Z
2021-01-11T19:54:12.817Z
Yakk
<p>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).</p>
<p><a href="https://github.com/akowald/CHIP-8/blob/master/chip8.cpp#L538" rel="nofollow noreferrer">Here</a> 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 <a href="https://en.wikipedia.org/wiki/CHIP-8#Opcode_table" rel="nofollow noreferrer">wikipedia</a>.</p>
<p>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.</p>
<p>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.</p>

CC BY-SA 4.0
2021-01-12T10:18:01.693Z
2021-01-12T10:18:01.693Z
lyinch
<p>What may be the very best algorithm for demonstrating the value of bit shifts is <em>division!</em> Everyone learning CS should have very solid intuitions around division, and <em>trying to divide two numbers using only addition, subtraction, bit shifts and comparison</em> is a wonderful demonstration of the power of bit shifting.</p>
<p>I would go through two steps (levels of enlightenment, if you will):</p>
<ol>
<li><strong>Division using repeated subtraction</strong> of the divisor from the dividend. Easy enough to understand, but gets inefficient with big numbers, as it scales with O(n)</li>
<li><strong>Division using repeated subtraction of powers of two</strong> 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))</li>
</ol>
<p>It's a great problem for 3 reasons:</p>
<ul>
<li><strong>No explanation of the problem needed</strong>: Everyone already knows what division is, and has a solid understanding of how it works</li>
<li><strong>The inefficient, non-bit-shifty solution is easy</strong>: 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</li>
<li><strong>There are multiple variants of the bit-shifty solution</strong>: For those who struggle to grasp the first variant of the bit-shifty solution, <a href="https://leetcode.com/problems/divide-two-integers" rel="nofollow noreferrer">there are several alternatives</a> 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</li>
</ul>

CC BY-SA 4.0
2021-01-13T19:55:48.320Z
2021-01-13T19:55:48.320Z
TheEnvironmentalist
<p>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.</p>
<p>Now I use Win32 API <a href="https://msdn.microsoft.com/en-us/library/windows/desktop/ms724439(v=vs.85).aspx" rel="nofollow noreferrer">GetVersion()</a>: 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.</p>
<p>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).</p>
<p>The language is C++. Students are 1st year, not pure CS (industrial automation).</p>

CC BY-SA 4.0
2021-01-10T22:57:14.763Z
Industrial automation? Go right to a microcontroller with its peripheral registers, which often need individual bit manipulation.
Bergi
CC BY-SA 4.0
2021-01-11T12:53:06.820Z
@Bergi the only time I use bit-manipulation in work is a few SPI devices (that I interface to a Raspberry Pi)
Chris H
CC BY-SA 4.0
2021-01-11T19:24:59.217Z
@Bergi There's a class dedicated to microcontrollers later in the curriculum. Mine is about software engineering in general and there's only one lesson for bits topic (because one has to deal with bits here and there). Hardware would be an overkill, unfortunately.
PlushBeaver
CC BY-SA 4.0
2021-01-12T14:08:38.653Z
@ChrisH The Raspberry Pi runs on a microprocessor, not quite a traditional microcontroller (though marketing people have called some Celeron chips microcontrollers which muddies the waters somewhat but old-school embedded programmers don't think of them as microcontrollers, we created a new name for them instead: SOC). What you normally do in config files on the Raspberry Pi you'd flip bits of individual memory addresses on microcontrollers.
slebetman
CC BY-SA 4.0
2021-01-12T14:17:56.943Z
@slebetman absolutely true. I also work with Arduinos which really are microcontroller-based (and in one case connected to an RPi  over TTL-232).  I was more commenting on the SPI aspect - the RPi is just a handy way of playing with SPi. 10 bits of ADC data or 12 bits of temperature data packed into 2 bytes, in an illogical order requires a bit of fiddling and shifting.  Configuring devices requires bit-masking config values.
Chris H
CC BY-SA 4.0
2021-01-12T14:18:30.380Z
... This is getting a bit much for comments, but my thinking was RPi (or Linux box with something like Adafruit's FT232H breakout board) and some SPI devices on the other end to replace the Win32 stuff (which is all PC-based)
Chris H
CC BY-SA 4.0
2021-01-13T23:55:50.170Z
Perhaps: Decoding the std::ios_base::openmode bitmask (e.g., mode codes for fstream::open)? https://www.cplusplus.com/reference/ios/ios_base/openmode/
Daniel R. Collins
<programming>
Realistic task for teaching bit operations
# Realistic task for teaching bit operations

(Asked by: username_0 on 2021-01-10)

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()](https://msdn.microsoft.com/en-us/library/windows/desktop/ms724439(v=vs.85).aspx): 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).

**Tags:** programming

> **Comments:**
> **username_1**: Industrial automation? Go right to a microcontroller with its peripheral registers, which often need individual bit manipulation.  
> **username_2**: @username_1 the only time I use bit-manipulation in work is a few SPI devices (that I interface to a Raspberry Pi)  
> **username_0**: @username_1 There's a class dedicated to microcontrollers later in the curriculum. Mine is about software engineering in general and there's only one lesson for bits topic (because one has to deal with bits here and there). Hardware would be an overkill, unfortunately.  
> **username_3**: @ChrisH The Raspberry Pi runs on a microprocessor, not quite a traditional microcontroller (though marketing people have called some Celeron chips microcontrollers which muddies the waters somewhat but old-school embedded programmers don't think of them as microcontrollers, we created a new name for them instead: SOC). What you normally do in config files on the Raspberry Pi you'd flip bits of individual memory addresses on microcontrollers.  
> **username_2**: @username_3 absolutely true. I also work with Arduinos which really are microcontroller-based (and in one case connected to an RPi  over TTL-232).  I was more commenting on the SPI aspect - the RPi is just a handy way of playing with SPi. 10 bits of ADC data or 12 bits of temperature data packed into 2 bytes, in an illogical order requires a bit of fiddling and shifting.  Configuring devices requires bit-masking config values.  
> **username_2**: ... This is getting a bit much for comments, but my thinking was RPi (or Linux box with something like Adafruit's FT232H breakout board) and some SPI devices on the other end to replace the Win32 stuff (which is all PC-based)  
> **username_4**: Perhaps: Decoding the std::ios_base::openmode bitmask (e.g., mode codes for fstream::open)? https://www.cplusplus.com/reference/ios/ios_base/openmode/  

---

## 13 answers

### Answer by username_7 on 2021-01-11. Score: 3 | Accepted answer

**varints**

Implement encoding and decoding something like [Protobuf's varint](https://developers.google.com/protocol-buffers/docs/encoding#varints), 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](https://en.wikipedia.org/wiki/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 by username_8 on 2021-01-11. Score: 27

Maybe a bit too complicated, but fun nevertheless: Teach them about [bitboards](https://en.wikipedia.org/wiki/Bitboard).

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.

> **Comments:**
> **username_9**: And you just gave me an afternoon self-study idea :D  
> **username_10**: It would take one more 64-bit integer to keep track of the en-passant states of the pawns (just use `1` on any space that contains a pawn that has done it), and since the rules of promotion REQUIRE that pawns promote when they reach the end of the board, the two end rows can safely be used to store information about whether that team has castled.  So, I believe that means you can store a full game state in 8 64-bit ints, with 14 bits of information left over in those two castling rows.  6 for the piece types, one for color, and one for en-passant and castling.  Neat!!  
> **username_11**: @BenI: See also [Smallest chess board compression](https://codegolf.stackexchange.com/questions/19397/smallest-chess-board-compression) challenge on [codegolf.se].  
> **username_12**: Truly excellent and interesting answer. Thanks.  
> **username_13**: You can use bitboards for tic-tac-toe and simpler games if chess is out of scope.  

---

### Answer by username_10 on 2021-01-10. Score: 8

Possibly prior to username_14'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.

> **Comments:**
> **username_14**: I should note that the [IBM 7030 Supercomputer](https://en.wikipedia.org/wiki/IBM_7030_Stretch) and their first transistorized computer, didn't have an "adder". It used table lookup to provide addition. It's nickname inside IBM was CADET (Can't Add, Doesn't Even Try). I knew the guy that gave it this name.  
> **username_14**: Some engineers came to my colleague (hallway conversation) and said that they were having trouble designing an adder (remember, this was long ago) and that the result would be overly expensive - a substantial fraction of the cost. Bill suggested table lookup from which the nickname arose.  
> **username_10**: @username_14 That is an amazing story!  
> **username_14**: Hmmm. I'm getting CADET hits for the [1620](https://en.wikipedia.org/wiki/IBM_1620) instead. Perhaps I remember it wrong. Sneaky synapses.  
> **username_14**: If you can do subtraction with only bit operations (yes, you can) then you can do square roots with only bit operations.  
> **username_16**: I quite like number 1 here (and subsequently number 2). When I was first learning to do bitwise operations, I wasn't really sure what a practical application for them was, but I did find that this was a very fun thing to learn. It's also not overly complicated and can easily be solved on paper and implemented accordingly.  
> **username_0**: After you mentioned case-insensitive string comparison, I started thinking about UTF-8 and varint encoding/decoding. Typically it's library stuff, but used almost everywhere.  
> **username_17**: The IBM 7030 Stretch had two arithmetic units with multiple carry-propagate adders and carry-save adders. (@username_14, you're thinking of the IBM 1620 which used table lookup.) The 7030's adders are described in http://www.bitsavers.org/pdf/ibm/7030/Bloch_EngrDesOfStretch_1959.pdf  
> **username_18**: @username_14 I have a vague memory of an ancient book of "programming problems/exercises for the 1620" which included overwriting the arithmetic tables to work in different number bases.  

---

### Answer by username_14 on 2021-01-10. Score: 6

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.

> **Comments:**
> **username_0**: Large bitmap as an integer set representation is a good choice, there are even more applied tasks it's used for. STEM students are familiar with the sieve of Eratosthenes, however, searching for prime numbers won't look very practical to them.  
> **username_15**: @username_0 Both PostgreSQL and Elasticsearch combine index search results by mapping documents/rows to bits in a bitmap and then combining them using bit operations on them. Maybe that's more practical.  

---

### Answer by username_19 on 2021-01-12. Score: 4

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 by username_11 on 2021-01-11. Score: 4

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](http://www.cplusplus.com/reference/bitset/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**](https://en.wikipedia.org/wiki/Bloom_filter). The bit operations needed are similar to [username_14's prime number sieve example](https://cseducators.stackexchange.com/a/6731), 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**](https://en.wikipedia.org/wiki/Linear-feedback_shift_register), and use it to [calculate a cyclic redundancy checksum](https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks). CRCs are everywhere in industry, and knowing how they work is certainly useful. And LFSRs have plenty of [other uses](https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Applications) as well.
* As an extension of the above, implement a [**stream cipher**](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Trivium_(cipher)) 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](https://crypto.stackexchange.com/questions/2700/galois-fields-in-cryptography/2718#2718) and have them implement [**arithmetic operations in GF(2*n*)**](https://en.wikipedia.org/wiki/Finite_field_arithmetic) 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](https://crypto.stackexchange.com/questions/12956/multiplicative-inverse-in-operatornamegf28/12962#12962); 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(28), use it to implement the [AES S-box](https://en.wikipedia.org/wiki/Rijndael_S-box), and then actual [**AES encryption**](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard). 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](https://en.wikipedia.org/wiki/AES_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](https://crypto.stackexchange.com/questions/20228/consequences-of-aes-without-any-one-of-its-operations).)
* 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](http://vyznev.net/corewar/guide.html)" language used in [**Core War**](https://en.wikipedia.org/wiki/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**](https://graphics.stanford.edu/%7Eseander/bithacks.html) 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](https://graphics.stanford.edu/%7Eseander/bithacks.html#ModulusDivisionEasy),
* [checking whether an integer is a power of 2](https://graphics.stanford.edu/%7Eseander/bithacks.html#DetermineIfPowerOf2), or
* [counting the number of 1 bits in an integer](https://stackoverflow.com/questions/22081738/how-does-this-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer-work).

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


---

### Answer by username_20 on 2021-01-11. Score: 3

One I've used is an algorithm which solves [Latin squares](https://en.wikipedia.org/wiki/Latin_square) (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 by username_21 on 2021-01-10. Score: 2

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/%7Efsieker/CurrentSemester/assignments/FIELD/doc)

[https://www.cs.colostate.edu/~fsieker/CurrentSemester/assignments/FLOAT.C/doc](https://www.cs.colostate.edu/%7Efsieker/CurrentSemester/assignments/FLOAT.C/doc)


---

### Answer by username_22 on 2021-01-11. Score: 2

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;
using scanline = std::span;

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 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 interlace( std::span );

// take any number of channels, and interlace them width bits at a time
std::vector interlace( std::span, 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, int x, int y, int size );

Calls shift or rotate:
void do_pan( std::span, int dx, int dy, bool bWrap=false );

Copies src multiple times over dst -- calls blit and shift.
void tile( std::span src, std::span dst, int offsetx, int offsety );

Instead, calls blit and rotate:
void tile2( std::span src, std::span 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 )
void zoom_x4( std::span )

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 by username_23 on 2021-01-12. Score: 2

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](https://github.com/akowald/CHIP-8/blob/master/chip8.cpp#L538) 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](https://en.wikipedia.org/wiki/CHIP-8#Opcode_table).

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 by username_24 on 2021-01-13. Score: 2

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](https://leetcode.com/problems/divide-two-integers) 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 by username_5 on 2021-01-29. Score: 1

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 by username_6 on 2021-01-12. Score: 0

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).


---

