Binary Tricks

Last Update

Introduction

Here I share a list of binary operations I have found/seen from books and codes from other programmers, that I find them intrigued and useful (at least for me).

Testing if a Number is even

While many would use modulus 2, to test a number is even or not, you simply check the least significant bit (lsb) of the number is 1 (odd) or 0 (even). For example, \[19283_{10} \land 1 = 1 (odd)\] \[284_{10} \land 1 = 0 (even)\]

"Fast" Modulus

This is actually an extension of the knowledge from the last part. In the last section, AND 1 is used to replaced the modulus of 2, to test if number is even (divisible by 2).

But I would like to take this furthur a bit, by understanding that if a number \(x\) is not divisible by \(y\), the remainder \(r\) of the division will consists of integer in the range of \(r \in [0,y-1] \). For example, 13 is not divisible by 5, and the remainder is 3, 14 is not too and remainder yields 4.

Here we observe one pattern, for number that's \(2^n\) where \(n\) is positive integer, if you take any numbers divided by it, the remainder will be in range of \([0, 2^n - 1]\). For example, is the divisor is 8, the remainder will be one of \(0, 1, 2, ... 7\).

We can observe, that when getting remainder of a number divided by divisor that's \(2^n\), or going back to our topic, to perform the modulus operation of a number against \(2^n\), the remainder is actually falls at those bits that's at position less than \(2^n\). To extract those bits out, simply we can use a AND operator, or namely \[x \mod 2^n \equiv x \land 2^n - 1\]

The AND \(2^n - 1\) will mask out every bit that's before \(2^n\). Let's consider the following examples: $$ 156 \mod 16 = 12 \equiv 156 \land (16 - 1) = 12$$ $$ \begin{array} {|r|r|}\hline & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ \hline \land & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline \end{array}$$

So you just turn a long division problem to a bitwise operation. That's the power of 2!

Taking out the least significant 1

We all know 2's complement, just a reminder, it's used to represent negative number in computers. Here is the procedure of getting a 2's complement of a number

  1. Inverting all bits, e.g. 5 in binary \(0101\), inverting all bits \(1010\)
  2. Add 1 to the inverted number, e.g. \(0101 + 1 = 1011\)
If we take a number and AND with its 2's complement, surprisingly (for me) it will yield the value of the least significant 1 in the number. Let's take 6 for example, its binary is \(0110\) and its 2's complement is \(1010\), performing AND operation as described, \begin{array} {|r|r|}\hline & 0 & 1 & 1 & 0 \\ \hline \land & 1 & 0 & 1 & 0 \\ \hline & 0 & 0 & 1 & 0 \\ \hline \end{array} The result is \(2_{10}\) or \(0010_{2}\), if not surprised, the least significant 1 of 6 is actually at the position where \(2^1\)

Padding

In programming quite often you will see problem such as finding the required number of character(s) ,\(n\), to pad in front of a string of length \(s\) such that \(n + s\) is a multiple of some integer \(i\). For example, in AES-128 encryption, which requires one to provide a plain text of multiple of 16 bytes, and if not you have to pad it until its length is multiple of 16 bytes.

Provided such problem statement, one would naturally comes out with the following simple solution:

  1. Starting from its current length \(s\), check if it's multiple of the integer \(i\) by using the modulus (checking if \(s \mod i\) is zero)
  2. If it's not, increment the number by 1, repeat step 1, until its final length is multiple of \(i\)

This approach is not that bad, after all, the worst we could go for the 16 bytes case is to iterate 15 times.

However, if the final length of the padded array/text/string is a multiple of power of 2, the following bitwise operation can gives you the required pad length in a one line $$ pad \ length = (\neg s + 1) \land (i - 1) $$ The left operand of AND is the 2's complement of the original string length \(s\); \(i\) is the "block size" that will wholly divide the final length of the string

One thing to note that this only works, if the final length of entity has to be multiple of \(2^n\).

For example, an string of length 13, has to be padded with '0' until its length is of multiple of 16 (\(2^4\)), find the number of '0' required to pad. \[\begin{align} pad \ length &= (\neg 1101_2 + 1_2) \land (00010000_2 - 1_2) \\ &= 0011_2 \land 1111_2 \\ &= 0011_2 \\ &= 3_{10} \end{align}\]

So we need to pad another 3 character to make 13 becomes 16, which makes sense. Reader can try for other length and see the result.