Part 1: Bits 101

A contract on naming conventions before diving into bitwise operations and algorithms

An example of a bit word, interpreted as a binary number

So you made it past the intro! Congratulations and thanks. Before we move on to covering more advanced and cooler content, let’s cover two basic definitions:

• A bit is any digit that can take the value 0 or 1. A bit alone does not do much; to create information, you will need:
• Bit strings, or sequences of bits, e.g., 01011101101. A bit string of length n can referred to as an n-bit string or n-bit word (as seen in Federal Information Processing Standards). For instance, an octet is a 8-bit word.

Secondly, a few properties which I find useful to remember at all times when dealing with bits:

• Bit strings is all your computer knows. All information that gets processed or stored on your device passes through a state where it is represented only as a series of 0s and 1s. A key stroke, a scroll, a connection to a website, any image or file… can be written as a series of bit strings.
• Bit strings are not just the base-2 representations of numbers. In fact, I find it useful to consider bit strings through two different lenses:

Bits strings as binary numbers. In this interpretation, bit strings are simply numbers; ‘truth-y’ bits in position i are worth 2ⁱ, and bit strings are equal to the sum of their bits (more about the general concept in this Wikipedia article).

Here, the binary representation is a contingency, useful to understand and define specific functions that will run fast on computers given their binary architectures. However, because the notation does not convey meaning in itself, binary numbers and functions are as well described in any arbitrary base, for example base 10 for humans, or base 16 (hexadecimal) for conciseness.

Bits strings as language. In this view, bit words are more similar to human words: each bit, as a letter, helps form a bit word; letters do not increase the “value” of words but do change their meanings; converting words to numbers is possible but counterproductive.

As an example, think of “pear” and “peer”: the difference in meaning between these words is useful, but the fact that their number value would be different — if you were to convert — is irrelevant. Likewise, in this interpretation of bit strings, we consider that 10001 and 11001 differ in an interesting way, not because their base-10 value is different, but because their meaning, according to a defined grammar, is different. We find such grammars (though they may not be called as such) in UTF-8 encoding, in bit flags, or in padding steps for encryption and hashing algorithms.

With those definitions and concepts in mind, we are ready to move into the world of bitwise operations, starting with the simpler ones: shifts, rotations, additions, AND, OR, XOR.

See you soon!