Bit Manipulation

Bit manipulation is an advanced topic that JavaScript developers typically do not need to know. Low-level programming languages such as C take advantage of these operators. However, you should learn a bit about bit manipulation if you want to implement high-performance server-side code.

Understanding bit manipulation requires some knowledge of digital logic. Any introductory course in discrete math or circuits would be helpful to understand these concepts.

Bitwise Operators

Here are the bitwise operators in JavaScript:

& : AND
| : OR
~ : NOT
^ : XOR
<<: Left shift
>>: Right shift
>>>: Zero-fill right shift

Note

Recall from Chapter 3 that all numbers are represented with 32 bits (meaning there are 32 1s and 0s). When converting from decimal numbers (base 10) to binary (base 2), it is important to keep this in mind.

AND

The AND operator is true when both bits are 1. The & (ampersand) is used for the AND operator.

a b a AND b

0 0 0

0 1 0

1 0 0

1 1 1

In bitwise operations, the numbers are in binary representation. For example, 9 in binary is 1001, and 5 in binary is 101.

For each bit, the AND operation has to be performed:

9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

9 & 5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 1

1 console.log(9 & 5); // prints 1

Here’s another example:

40 in base 10 = 100010 in base 2

41 in base 10 = 100011 in base 2

40: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0

41: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1

40 & 41: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 = 40

OR

The OR operator is when either bit is 1. The | (pipe) is used for the OR operator.

a b a OR b

0 0 0

0 1 1

1 0 1

1 1 1

Let’s use 9 | 5 and 40 | 41 as examples .

9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

9 | 5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 = 13

Here’s another example:

40: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0

41: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1

40 & 41: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 = 41

XOR

XOR means “exclusive or.” It evaluates to true only when one of the bits is 1. The ^ (caret) is used for the XOR operator.

a b a XOR b

0 0 0

0 1 1

1 0 1

1 1 0

9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

9 ^ 5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 = 12

40: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0

41: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1

40 ^ 41: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 1

NOT

The NOT operator inverses all bits. The ~ (tilde) is used for the NOT operator. Please do not confuse the NOT operator with the negative operator. Once the bits are inverted, the numbers in 32-bit follow.

a NOT a

0 1

1 0

Let’s take 9 and 5 as an example:

9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

~9: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 = -10

5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

~5: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 = -6

Left Shift

In left shift, all the bits are shifted to the left, and any excess bits shifted off to the left are discarded. The << (double left-angle brackets) is the operator of left shift.

9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

9 << 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 = 18

9 << 2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 = 36

Left shift often multiplies elements by 2 for each shift. This is because binary is a base 2 system, implying a left shift is equal to multiplying all the digits by 2. However, the shift can cause the bit to overflow and reduce the value.

1073741833: 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

1073741833 << 2: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 = 36

Right Shift

In right shift, all the bits are shifted to the right, and any excess bits shifted off to the right are discarded. The >> (double right angle brackets) is the operator for right shift.

9: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1

9 >> 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 = 4

-9: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1

-9 >> 2: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 = -3

In this example, shifting divided the 9 by 2 (integer division). This is because, again, binary is a base 2 system.

Zero-Fill Right Shift

In zero-fill right shift, all the bits are shifted to the right, and any excess bits shifted off to the right are discarded. However, the sign bit (the leftmost bit) becomes a 0 before the shift, and this results in a non-negative number. The >>> (triple right brackets) is the operator for the zero-fill right shift.

-9: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1

-9 >>> 1: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 = 2147483643

In this example, shifting divided the 9 by 2 (integer division). This is because, again, binary is a base 2 system.

To have a better understanding of why these operations work, it is recommended to take an introductory digital logic course in school or online. In the end, everything consists of 1s and 0s because a transistor in a computer can have only two states: on and off.

Number Operations

This section will cover how to perform addition, subtraction, multiplication, division, and modulus using bitwise operators.

Addition

Adding binary numbers is no different from adding decimal numbers. The rule that children learn in the second grade is the same: add up two numbers and carry 1 to next digit if it exceeds 10.

The function that implements this is as follows. You can find all the code on GitHub.¹

1 function BitwiseAdd(a, b){

2 while (b != 0) {

3 var carry = (a & b);

4 a = a ^ b;

5 b = carry << 1;

6 }

7 return a;

8 }

10 console.log(BitwiseAdd(4,5)); // 9

Here are two examples in detail:

bitwiseAdd(4, 5);

4: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

5: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1

sum = 4 ^ 5 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 = 1 (base 10)

carry = (a & b) << 1

a & b = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0

(a & b) << 1 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 = 8 (base 10)

bitwiseAdd(1, 8);

1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

8: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

sum = 1 ^ 8 = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 = 9 (base 10)

carry = (a & b) << 1

a & b = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

-> return 9 (a)

Subtraction

Subtraction is the difference of two numbers. However, you can also think of it as adding a negative number. Here’s an example: 5 - 4 = 5 + (-4).

Therefore, first create a negate function using the NOT operator. In binary, subtracting a negative binary number from a positive one is obtained by inverting all the bits and adding 1. This is implemented in the following code block:

1 function BitwiseNegate(a) {

2 return BitwiseAdd(~a,1);

3 }

5 console.log(BitwiseNegate(9)); // -9

6 // negation with itself gives back original

7 console.log(BitwiseNegate(BitwiseNegate(9))); // 9

9 function BitwiseSubtract(a, b) {

10 return BitwiseAdd(a, BitwiseNegate(b));

11 }

13 console.log(BitwiseSubtract(5, 4)); // 1

Multiplication

Multiplying numbers in base 2 follows the same logic as multiplying numbers in base 2; multiply the numbers, carry anything over 10 to the next digit, and then multiply the next digit with the shifted base (in the case of decimals, multiply by 10 each time you shift the digit). For example, 12 times 24 is done by first multiplying 2 and 4, then 10 and 4, then shifting the digit to 2 (20 now), multiplying 20 and 2, and then multiplying 20 times 10. Finally, add those values up to obtain 288.

------

288

In binary:

0 1 1 0 0

1 1 0 0 0

-----------------

0 0 0 0 0

0 1 1 0 0

-------------

1 0 0 1 0 0 0 0 0

The following code block illustrates this implementation, and it also handles negative numbers:

1 function BitwiseMultiply(a, b) {

2 var m = 1,

3 c = 0;

5 if (a < 0) {

6 a = BitwiseNegate(a);

7 b = BitwiseNegate(b);

8 }

9 while (a >= m && b) {

10 if (a & m) {

11 c = BitwiseAdd(b, c);

12 }

13 b = b << 1;

14 m = m << 1;

15 }

16 return c;

17 }

18 console.log(BitwiseMultiply(4, 5)); // 20

Division

Division can be thought of as the number of times you can subtract b from a, given a/b. For example, 4/2 = 2 because 4-2-2 = 0. Using this property, bitwise division can be implemented as follows:

1 function BitwiseDividePositive(a, b) {

2 var c = 0;

4 if (b != 0) {

5 while (a >= b) {

6 a = BitwiseSubtract(a, b);

7 c++;

8 }

9 }

10 return c;

11 }

12 console.log(BitwiseDividePositive(10, 2)); // 5

This is relatively simple for positive numbers. The while loop can keep subtracting, and a counter variable can store how many times b subtracted a. However, what about for negative numbers? -10 /2 = -5, but we cannot subtract 2 from -10 because the while loop would go on forever. To avoid this, convert both the numbers into positive numbers. Doing this, we have to keep track of the sign.

a b a * b

+ + +

+ - -

- + -

- - +

If negative is represented as 1 and positive as 0, this is the same table as an XOR table:

a b a * b

0 0 0

0 1 1

1 0 1

1 1 0

The division algorithm is shown next. This function subtracts b from a until it is zero. Again, negative numbers have to be handled appropriately at the end with a negation helper function.

1 function BitwiseDivide(a, b) {

2 var c = 0,

3 isNegative = 0;

5 if (a < 0) {

6 a = BitwiseNegate(a); // convert to positive

7 isNegative = !isNegative;

8 }

10 if (b < 0) {

11 b = BitwiseNegate(b); // convert to positive

12 isNegative = !isNegative;

13 }

15 if (b != 0) {

16 while (a >= b) {

17 a = BitwiseSubtract(a, b);

18 c++;

19 }

20 }

22 if (isNegative) {

23 c = BitwiseNegate(c);

24 }

26 return c;

27 }

29 console.log(BitwiseDivide(10, 2)); // 5

30 console.log(BitwiseDivide(-10, 2)); // -5

31 console.log(BitwiseDivide(-200, 4)); // -50

Summary

This chapter covered the basics of bit manipulation in JavaScript. Bit manipulation is used for high-performance numerical operations. Using bitwise operators is much faster than using the native methods in the Math class. With JavaScript advancing into server-side programming with Node.js, more efficient code is needed. To consolidate the concepts from this chapter, Table 20-1 summarizes bitwise operators and their usage.

Table 20-1

Bit Manipulation Summary

Operator	Operation	Use Case
&	AND	1 when both bits are 1
\|	OR	1 when either bit is 1
∼	NOT	Inverts all the bits
^	XOR	1 when only one of the bits is 1
<<	Left shift	Shifts to the left, and any excess bits are shifted off
>>	Right shift	Shifts to the right, and any excess bits are shifted off
>>>	Zero-fill right shift	Shifts to the right, and any excess bits are shifted off and the sign bit comes 0

20. Bit Manipulation

Bitwise Operators

Note

AND

OR

XOR

NOT

Left Shift

Right Shift

Zero-Fill Right Shift

Number Operations

Addition

Subtraction

Multiplication

Division

Summary