Bit Manipulation Part II

Image by Gerd Altmann from Pixabay

Last week I took a quick look at bit manipulation. I learned about bitwise operators, as well as how to represent positive base 10 numbers in binary (base 2). Today I want to dig a little deeper, and talk about negative numbers represented in binary, as well as a few clever bit manipulation tricks.

Negative Numbers

In my last blog I discussed how using the NOT (~) bitwise operator on a number in your code, would get you a different result than what I had shown. That’s because more than likely you’re dealing with 32-bit signed integers, which means that those 32 ones and zeroes, have to somehow account for both positive and negative numbers.

For simplicity’s sake, I will use 8-bit signed integers, but the concepts are the same as with their 32-bit counterparts. Now, let’s discuss how we convert a number to a negative in binary.

One’s Complement

One way to convert a number to negative in binary is by using one’s complement. This involves just inverting each bit. Because of this the number 0 has two representations using this method: 00000000, and 11111111. This denotes positive 0 and negative 0 respectively.

Let’s convert a few more numbers:
1 => -1
00000001 => 1111110
2 => -2
00000010 => 11111101
3 => -3
00000011 => 11111100

Using one’s complement, we can represent integers in the range -(2ⁿ⁻¹-1) to 2ⁿ⁻¹-1, where n represents the number of bits (so 8, in our example). So for an 8-bit signed integer, using one’s complement we can represent from -127 to 127.

Two’s Complement

Another way to convert binary numbers to a negative is to use two’s complement. Using two’s complement, the sum of a number and its complement is 2ⁿ (where n represents the number of bits, again). To do this by hand, you can invert all of the bits (just as we did with one’s complement) and then add 1. Because of this two’s complement only has one representation of 0, because 11111111 + 1, will result in 100000000 (9 bits), but the extra 1 is overflow and is therefor discarded, leaving us with 00000000.

Let’s convert some numbers:
1 => -1
000000001 => 11111110 + 1 => 11111111
2 => -2
00000010 => 11111101 + 1 => 11111110
3 => -3
00000011 => 11111100 + 1 => 11111101

JavaScript uses two’s complement, so you can try this for yourself. Enter ~ followed by some number + 1, and you should get the negative version of that number. That’s because the NOT bitwise operator inverts all of the bits for us, then we just need to add 1.

Using two’s complement all integers from -(2ⁿ⁻¹) to 2ⁿ⁻¹-1 can be represented. So for 8-bit signed integer, two’s complement could represent all integers from -128 to 127.

Signed Magnitude Representation

The signed magnitude representation of a binary number, is what may be more intuitive. The most significant bit (furthest to the left) denotes the sign (+/-), and the rest of the bits are the absolute value of the number. Because of this, we have both positive and negative 0 using signed magnitude representation, as well. That would be 00000000 and 10000000, respectively.

Let’s convert a few more numbers:
1 => -1
00000001 => 10000001
2 => -2
00000010 => 10000010
3 => -3
00000011 => 10000011

The range of integers that can be represented by signed magnitude representation can be determined by -(2ⁿ⁻¹-1) to 2ⁿ⁻¹-1, the same as one’s compliment.

Which Should We Use?

From my understanding, two’s complement is the most frequently used in modern day. I won’t go into it in this blog but that’s because arithmetic is simpler using two’s complement, and there isn’t a negative 0. In older computers and systems, it was common to see one’s complement being used. It’s also worth noting that signed magnitude representation is the most intuitive, as it’s how we are used to thinking about negative numbers, just prepending the number with a -.

Using Bit Manipulation to Solve Algorithms

We know how to represent numbers in binary, both positive and negative. Now let’s have some fun and solve some algorithms using bit manipulation!

Return The Only Non-Duplicate Number

This is the original problem which got me looking into bit manipulation. This is the problem description on leetcode:

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

So, before I knew anything about bitwise operations, I thought to use a hash table. The solution with a hash table had O(n) time complexity and O(n) space complexity.

However, you can use bitwise operators to come up with a solution that has O(n) time complexity and O(1) space complexity!

Code

function singleNumber(nums) {
    let answer = 0;
    for (let i = 0; i < nums.length; i++) {
        answer ^= nums[i];
    }
    
    return answer;
}

Explanation

Remember that ^ is the XOR operator, XOR takes two bit patterns and if the bits in the corresponding position are opposite, it puts a 1 in that position. What this means is, some number XOR itself, returns 0. As every number will be identical and therefor there will be no opposites. In addition to this, 0 XOR some number, returns that number. This makes logical sense because 0 is all zeroes in binary, and therefor, the ones will be in the same positions, as that is where they are opposite 0, and give us the same number.

So, all of the duplicates will cancel one another out, leaving us with 0, which then when we XOR 0 with the non-duplicate, it will return that number!

Power of Two

How do we determine if a number is a power of 2? The naïve solution may be to see if a number is divisible by 2, then if it is divide it, and continue that approach until we reach 1 (in which case it is a power of 2).

Using bit manipulation we can determine this much more simply!

Code

function isPowerOfTwo(n) {
    return (n > 0) && !(n & (n - 1));
}

Explanation

First off, anything less than or equal to 0 cannot be a power of 2. The next important thing to think about is that binary is in base 2 that means that having just one bit set (a bit being set means that it is 1, not 0), is a power of two. To understand this, let’s look at the powers of 2 represented in binary.

2⁰ => 1 => 00000001
2¹ => 2 => 00000010
2² => 4 => 00000100
2³ => 8 => 00001000
2⁴ => 16 => 00010000
2⁵ => 32 =>00100000
2⁶ => 64 => 01000000
2⁷ => 128 => 10000000

So then comes the question, how do we figure out if just 1 bit is set? This is what the !(n & (n - 1)) part of our code is doing. Let me explain:

Any number which only has 1 bit set, that number - 1 is going to have every bit preceding that bit set. Again, this is easier to understand if you look at it.

2 = 00000010 and 1 = 00000001
4 = 00000100 and 3 = 00000011
8 = 00001000 and 7 = 00000111
and so on…

This means that we can use the & operator, because a bit will only be set if it is set in both series of bits. This means that if a number is a power of two, that number & that number - 1, should equal 0, because they will not have a set bit in any of the same positions. 0 is a falsey value, and that is why we use the ! operator.

Divisible by Two

Before learning about bitwise operators, I used to use % to determine if a number was divisible by two. I would just return n % 2 === 0. Simple enough right? Well it can be optimized slightly with bit manipulation.

function isEven(n) {
    return n & 1 === 0;
}

Truly, the difference in speed is minimal, but here is an article which measures the increase in performance.

It is worth noting, you can replace % with & for any power of 2, for the same reasons mentioned in the above. Except, rather than n & 1 it would be & the number you’re checking to see if its divisible by minus 1. Let’s show this in some code.

function isDivisibleBy(n, m) {
    // checking if m is a power of 2
    if ((m > 0) && !(m & (m - 1))) {
        return (n & (m - 1)) === 0;
    } else {
        return n % m === 0;
    }
}

Explanation

We are checking to see if n is divisible by m. We know we can only use & if m is a power of 2, if it’s not we will default to using %.

This works because:
2 - 1 = 1 = 00000001
2 = 00000010
4 = 00000100
6 = 00000110

Notice none of the numbers divisible by 2 have a bit set in the first position?

Let’s see it with a different power of 2:
4 - 1 = 3 = 00000011
4 = 00000100
8 = 00001000
12 = 0001100

We see the same patter, anything divisible by 4 won’t have bits set in the first two positions.

I don’t recommend using that function in particular because it does the extra work of checking that the divisor is a power of two. However, if you happen to know it is a power of two, or you’re simply checking if a number is even or odd, you can use bit manipulation to slightly optimize your code.

In Conclusion…

I’m not a stickler when it comes to optimization (I prioritize readability), however it is undeniable that many of these bit manipulation tricks are really cool. I look forward to learning about more of them, and hope that I can learn to spot places in my code that can be quickly optimized using bit manipulation.