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

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

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

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

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?

Using Bit Manipulation to Solve Algorithms

Return The Only Non-Duplicate Number

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

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

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…

Aspiring Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store