JavaScript and Bit-hacks 🧙🏻‍♂️

May 01, 2020 ∙ 👩🏻‍🏫 13 min

Bitwise operators operate on binary numbers. If the operands of a bitwise operator are not binary, then they are converted into binary before the operation.

In JavaScript, bitwise operators convert their operand(s) into 32-bit signed integers in two’s complement format. However, the results are standard numbers. This post elaborates on bitwise operators available in JavaScript and explores a few popular bitwise tricks/hacks.

Before we jump into bitwise operators, let’s take a gander at the two’s complement.

There are many ways to compute two’s complement of a number. Here’s a one I like to use:

1. Convert the magnitude of the number to binary.
2. If the number is positive, then we are done.
3. If the number is negative:
   a. Find the one's complement of binary by inverting 0's and 1's.
   b. Add 1 to the one's complement.

Let’s find two’s complement of 5 and -5 with the method above. We’ll use a nibble(4 bits) for the same.

Finding two’s complement of 5 is straightforward. It’s a positive number. Therefore it’s two’s complement is 0101.

Finding two’s complement of -5 includes the following steps:

1. The magnitude of -5 is 5. 5 in binary is `0101`.
2. -5 is a negative number:
   1. The one's complement of `0101` is `1010`.
   2. The complement after adding 1: `1011`.

The two’s complement of -5 is 1011.

Converting two’s complement to decimal involves similar steps.

1. If the two's complement of the number starts with `1`:
   a. Find the one's complement by inverting 0's and 1's.
   b. Add one to the one's complement.
2. Convert the binary to decimal.
3. If two's complement starts with one, add minus sign to decimal.

Let’s consider two’s complement 0101 and 1011 and find their decimal values.

0101 starts with zero. It doesn’t require any additional steps. The decimal value of 0101 is 5.

The two’s complement to decimal conversion for 1011 requires the below steps:

1. One's complement of `1011` is `0100`.
2. After adding 1: `0101`.
3. The decimal equivalent of `0101` is 5.
4. `1011` starts with one. Therefore, -5.

The decimal value of 1011 is -5.

In two’s complement format, the leftmost bit acts as a sign bit. It means an n-bit layout can safely represent numbers from -2^{n - 1} to 2^{n - 1} - 1 in two’s complement format. For example, a nibble(4 bits layout) can represent number from -8 to 7 without any precision loss.

JavaScript uses a 32-bit layout for bitwise operations. Therefore, the range is -2³¹ to 2³¹ - 1(equivalent to -2147483648 to 2147483647).

Two’s complement of some numbers in 32 bits:

-1

          1 => 00000000000000000000000000000001
 Complement => 11111111111111111111111111111110
                                             +1
-----------------------------------------------
2's complement 11111111111111111111111111111111
-----------------------------------------------

2147483647

 2147483647 => 01111111111111111111111111111111
-----------------------------------------------
2's complement 01111111111111111111111111111111
-----------------------------------------------

-2147483648

 2147483648 => 10000000000000000000000000000000
 Complement => 01111111111111111111111111111111
                                             +1
-----------------------------------------------
2's complement 10000000000000000000000000000000
-----------------------------------------------

If a number has more than 32-bits, it looses its significant bits. For example, the below statement logs zero.


console.log((2 ** 32) >> 0);

It is because the 2’s complement of 2³² is zero in 32-bits. We shift zero by zero bits and end up with zero.

    4294967296 => 100000000000000000000000000000000 (33 bits)
    4294967296 =>  00000000000000000000000000000000 (32 bits)
-------------------------------------------------------------
2's complement =>  00000000000000000000000000000000 (32 bits)
-------------------------------------------------------------

Bitwise Logical Operators

Bitwise logical operators pair each bit of one operand with another operand and perform logical operations on these pairs. That’s why these operations are called bitwise operations.

& (Bitwise AND)

& operator performs AND operation. It yields 1 if both operands are 1, else 0.

x	y	x & y
0	0	0
0	1	0
1	0	0
1	1	1

     1 => 00000000000000000000000000000001
     2 => 00000000000000000000000000000010
------------------------------------------
 1 & 2 => 00000000000000000000000000000000  => 0
------------------------------------------

For any number x, x & 0 always yields 0.

| (Bitwise OR)

| operator performs OR operation. It yields 1 if one of the operand is 1, else 0.

x	y	x \| y
0	0	0
0	1	1
1	0	1
1	1	1

     1 => 00000000000000000000000000000001
     2 => 00000000000000000000000000000010
------------------------------------------
 1 | 2 => 00000000000000000000000000000011  => 3
------------------------------------------

For any number x, x | 0 always yields x.

^ (Bitwise XOR)

^ operator performs XOR operation. It yields 1, if both operands are different, else 0.

x	y	x ^ y
0	0	0
0	1	1
1	0	1
1	1	0

     1 => 00000000000000000000000000000001
     2 => 00000000000000000000000000000010
------------------------------------------
 1 ^ 2 => 00000000000000000000000000000011  => 3
------------------------------------------

For any number x, x ^ 0 always yields x.

~ (Bitwise NOT)

~ operator performs NOT operation. It inverts bits of the operands.

x	~x
0	1
1	0

    -1 => 11111111111111111111111111111111
------------------------------------------
 ~(-1) => 00000000000000000000000000000000 => 0
------------------------------------------

For any number x, ~x always yields -(x + 1).

Bitwise shift operators

Bitwise shift operators work with two operands—left and right. The operator shifts the left operand by certain bit positions—defined by the right operand. The operator controls the direction of the shifting.

Bitwise shift operators convert their left and right operands into 32-bit signed integers in two’s complement format. Only the least significant 5-bits of the right operand are used cause the operator can shift 32 bits at max.

<< (Left Shift)

As the name suggests, the left shift operator shifts the first operand to the left by the specified number of bits. The operator discards bits from left and fills zero from the right.

               2 => 00000000000000000000000000000010
----------------------------------------------------
          2 << 5 => 00000000000000000000000001000000 => 64
----------------------------------------------------

     -2147483648 => 10000000000000000000000000000000
----------------------------------------------------
-2147483648 << 1 => 00000000000000000000000000000000 => 0
----------------------------------------------------

>> (Sign-propagating Right Shift)

Sign-propagating right shift operator shifts the first operand to the right by the specified number of bits. It discards bits from the right and copies the leftmost bit on the left.

               2 => 00000000000000000000000000000010
----------------------------------------------------
          2 >> 1 => 00000000000000000000000000000001 => 1
----------------------------------------------------

     -2147483648 => 10000000000000000000000000000000
----------------------------------------------------
-2147483648 >> 4 => 11111000000000000000000000000000 => -134217728
----------------------------------------------------

>>> (Zero-fill Right Shift)

Zero-fill right shift operator is quite akin to sign-propagating right shift operator. Instead of propagating the sign bit, it fills zeros in the left while shifting the operand to the right.

Unlike other bitwise operators, zero-fill right shift operator returns a 32-bit unsigned integer. Therefore, the return value is converted directly from binary to decimal.

      -2147483648 => 10000000000000000000000000000000
-----------------------------------------------------
-2147483648 >>> 2 => 00100000000000000000000000000000 => 536870912
-----------------------------------------------------

      -2147483648 => 10000000000000000000000000000000
-----------------------------------------------------
-2147483648 >>> 0 => 10000000000000000000000000000000 => 2147483648
-----------------------------------------------------

Bitmask

A bitmask or mask is a variable that is used in bitwise operations to set/unset the bits of another variable. For example, let’s say we need to check if a variable is odd. How do we find it using bitwise operators? We know that the lowest bit of an odd number is always 1. The below function leverages this fact.


function isOdd(x) {
  return x & 1;
}
console.log(isOdd(5)); // 1
console.log(isOdd(4)); // 0

The function isOdd unsets bits of x by ANDing x with 1.

   5 => 0000000000000000000000000000101
   1 => 0000000000000000000000000000001
---------------------------------------
   & => 0000000000000000000000000000001 => 1
---------------------------------------

   4 => 0000000000000000000000000000100
   1 => 0000000000000000000000000000001
---------------------------------------
   & => 0000000000000000000000000000000 => 0
---------------------------------------

Here, we can say that 1 is acting as a mask/bitmask. Therefore, isOdd can be written as:


function isOdd(x) {
  const mask = 1;
  return x & mask;
}
console.log(isOdd(5)); // 1
console.log(isOdd(4)); // 0

You can read more about bitmask here.

Tricks

Bitwise tricks feel like the dark magic of computer programming 🔮. They are less intuitive and hard to understand. That’s because they operate on binary, and binary is made for machines, not for humans. I’ll do my best to explain each trick as simple as possible. Please feel free to correct/add if there’s any gap.

⚠️ Tricks below are demonstrated only for learning purposes. One should vet them thoroughly before using them in a project. Also, these tricks might have integer overflow if there’s a need for more than 32-bits.

Truncate Integer


function truncate(x) {
  // Double tilde(~)
  return ~~x;
}
truncate(-1234.12); // -1234
truncate(1234.12); // 1234

The method above truncates the integer part of a number. It exploits the fact that JavaScript converts the operands of a bitwise operator into 32-bit signed integers in two’s complement format.

You may want to use Math.trunc() in your project.

Flip sign of an integer

For any integer x, ~x yields -(x + 1). Therefore,

~x + 1 => -(x + 1) + 1 => -x - 1 + 1 => -x


function negate(x) {
  return ~x + 1;
}

Increment/decrement by 1


function add1(x) {
  // -~x => -(-(x + 1)) => x + 1
  return -~x;
}

function subtract1(x) {
  // ~-x => -(-x + 1) => x - 1
  return ~-x;
}

Swapping values

Values of two variables can be swapped using XOR operator.


function swap(x, y) {
  x ^= y;
  y = x ^ y;
  x ^= y;
}

Power of two

If x is a power of 2, then for x - 1 only the right most bits will be on. Therefore, ANDing x with x - 1 will yield zero if x is a power of 2. For example

      4  => 00000000000000000000000000000100
  4 - 1  => 00000000000000000000000000000011 => 3
--------------------------------------------
    &    => 00000000000000000000000000000000 => 0
--------------------------------------------


function isPowerOf2(x) {
  if (x === 0) {
    return false;
  }
  return (x & (x - 1)) === 0;
}

isPowerOf2(2); // true
isPowerOf2(3); // false

Absolute Value

Let’s we want to find the absolute value of -5 without branching. As we know, for any x, ~x yields -(x + 1). So we can do ~(-5) + 1 to get 5.

   -5  => 11111111111111111111111111111011
 ~(-5) => 00000000000000000000000000000100
                                        +1
 -----------------------------------------
          00000000000000000000000000000101 => 5
 -----------------------------------------

We need to negate the number and add 1 only when the the number is negative. We can use below algorithm:

Create a bitmask for a number x by x >> 31. The bitmask will be zero for positive x and -1 for negative x.

 5 >> 31 => 00000000000000000000000000000000 => 0

-5 >> 31 => 11111111111111111111111111111111 => -1

XOR bitmask with x to find negation.

x ^ 0 => x
x ^ -1 => ~x

Subtract bitmask.

(x ^ 0) - 0 => x;
(x ^ -1) => ~x - (-1) => ~x + 1

Above steps in JS code.


function abs(x) {
  const mask = x >> 31;
  return (x ^ mask) - mask;
}

You may want to use Math.abs() in your project.

Division/Multiply by 2

Division/multiplication by 2 can be achieved by shifting left/right by 1 bit.


function double(x) {
  return x << 1;
}

function half(x) {
  return x >> 1;
}

double(5); // 10
half(10); // 5

Detect sign


function hasSameSign(x, y) {
  return (x ^ y) < 0;
}

hasSameSign(-1, 1); // false;
hasSameSign(-1, -2); // true;
hasSameSign(2, 1); // true

Min and max of two integers

We can find min and max of two integers using XOR and comparison operator. For integers x and y, expression x < y evaluates to 1 if x is greater, otherwise 0 which means:

when x is greater.

-(x < y) => 0

// AND with 0.
(x ^ y) & -(x < y) => (x ^ y) & 0 => 0

// XOR with 0.
y ^ ((x ^ y) & -(x < y)) => y ^ ((x ^ y) & 0)  => y ^ 0 => y

when y is greater

-(x < y) => -1

// AND with -1.
(x ^ y) & -(x < y) => (x ^ y) & (-1) => x ^ y

// XOR with (x ^ y)
y ^ ((x ^ y) & -(x < y)) => y ^ ((x ^ y) & (-1)) => y ^ x ^ y => x


function min(x, y) {
  // If x is greater `mask` will be 0 otherwise -1
  const mask = -(x < y);

  return y ^ ((x ^ y) & mask);
}

function max(x, y) {
  // If x is greater `mask` will be 0 otherwise -1
  const mask = -(x < y);

  return x ^ ((x ^ y) & mask);
}

Alternate method. It uses the right shift operator and the difference in numbers.


function min(x, y) {
  // If x is greater `mask` will be 0 otherwise -1
  const mask = (x - y) >> 31;

  // (x - y) & 0 => 0
  // (x - y) & -1 => x - y
  return y + ((x - y) & mask);
}

function max(x, y) {
  // If x greater mask will be 0 otherwise -1
  const mask = (x - y) >> 31;

  // (x - y) & 0 => 0
  // (x - y) & -1 => x - y
  return x - ((x - y) & mask);
}

You may want to use Math.min() and Math.max() in your project.

Reverse bits of an unsinged integer


function reverseBits(number) {
  const size = 31; // 2's complement size.
  let result = 0;
  for (let i = 1; i <= 31; i += 1) {
    // Add the left most bit to `result`
    result |= number & 1;

    // Discard the added bit.
    number >>= i;

    // Make space for the new bit.
    result <<= 1;
  }
  return result;
}

console.log(reverseBits(1)); // -2147483648

RGB Values from color code


function hexToRgb(color) {
  const r = (color & 0xff0000) >>> 16;
  const g = (color & 0x00ff00) >>> 8;
  const b = color & 0x0000ff;
  return [r, g, b].join(', ');
}

console.log(hexToRgb(0x010203)); // 1, 2, 3

Final Thoughts:

In a high-level language like JavaScript, bitwise operators are relatively slow. The main reason for the slowness is the two’s complement conversion of the operands. Also, bitwise operators take a toll on the legibility of the code. Their less intuitiveness creates mental overhead of decimal to binary conversion and vice versa. One should use them sparingly.

Having said that, if the situation demands, don’t hesitate to shake some bits!

Hi, I am Hitesh.