LeetCode Meditations — Chapter 14: Bit Manipulation
Table of contents
We are in the last chapter of this series, and it's finally time to take a brief look at bit manipulation.
As Wikipedia defines it, a bitwise operation operates on a bit string, a bit array or a binary numeral (considered as a bit string) at the level of its individual bits.
Let's first represent a number in binary (base 2). We can use toString method on a number, and specify the radix:
const n = 17;
console.log(n.toString(2)); // 10001
const n = 17;
console.log(n.toString(2)); // 10001
We can also parse an integer giving it a base:
console.log(parseInt(10001, 2)); // 17
console.log(parseInt(10001, 2)); // 17
All bitwise operations are performed on 32-bit binary numbers in JavaScript. That is, before a bitwise operation is performed, JavaScript converts numbers to 32-bit signed integers.
So, for example, 17 won't be simply 10001 but 00000000 00000000 00000000 00010001.
After the bitwise operation is performed, the result is converted back to 64-bit JavaScript numbers.
Bitwise operators
AND (&)
If two bits are 1, the result is 1, otherwise 0.
const x1 = 0b10001;
const x2 = 0b101;
const result = x1 & x2; // 1 (0b1)
const x1 = 0b10001;
const x2 = 0b101;
const result = x1 & x2; // 1 (0b1)
OR (|)
If either of the bits is 1, the result is 1, otherwise 0.
const x1 = 0b10001;
const x2 = 0b101;
const result = x1 | x2; // 21 (0b10101)
const x1 = 0b10001;
const x2 = 0b101;
const result = x1 | x2; // 21 (0b10101)
XOR (^)
If the bits are different (one is 1 and the other is 0), the result is 1, otherwise 0.
const x1 = 0b10001;
const x2 = 0b101;
const result = x1 ^ x2; // 20 (0b10100)
const x1 = 0b10001;
const x2 = 0b101;
const result = x1 ^ x2; // 20 (0b10100)
NOT (~)
Flips the bits (1 becomes 0, 0 becomes 1).
const n = 17;
const result = ~n; // -18
const n = 17;
const result = ~n; // -18
If we use a helper function to see the binary representations, it is as we expected:
console.log(createBinaryString(n));
// -> 00000000 00000000 00000000 00010001
console.log(createBinaryString(result));
// -> 11111111 11111111 11111111 11101110
console.log(createBinaryString(n));
// -> 00000000 00000000 00000000 00010001
console.log(createBinaryString(result));
// -> 11111111 11111111 11111111 11101110
The leftmost bit indicates the signal — whether the number is negative or positive.
Remember that we said JavaScript uses 32-bit signed integers for bitwise operations.
The leftmost bit is 1 for negative numbers and 0 for positive numbers.
Also, the operator operates on the operands' bit representations in two's complement. The operator is applied to each bit, and the result is constructed bitwise.
Left shift (zero fill) (<<)
Shifts the given number of bits to the left, adding zero bits shifted in from the right.
const n = 17;
const result = n << 1; // 34
console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001
console.log(createBinaryString(34));
// -> 00000000 00000000 00000000 00100010
const n = 17;
const result = n << 1; // 34
console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001
console.log(createBinaryString(34));
// -> 00000000 00000000 00000000 00100010
Note that the 32nd bit (the leftmost one) is discarded.
Right shift (sign preserving) (>>)
Shifts the given number of bits to the right, preserving the sign when adding bits from the left.
const n = 17;
const result = n >> 1; // 8
console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001
console.log(createBinaryString(8));
// -> 00000000 00000000 00000000 00001000
const n = 17;
const result = n >> 1; // 8
console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001
console.log(createBinaryString(8));
// -> 00000000 00000000 00000000 00001000
const n = -17;
const result = n >> 1; // -9
console.log(createBinaryString(-17));
// -> 11111111 11111111 11111111 11101111
console.log(createBinaryString(-9));
// -> 11111111 11111111 11111111 11110111
const n = -17;
const result = n >> 1; // -9
console.log(createBinaryString(-17));
// -> 11111111 11111111 11111111 11101111
console.log(createBinaryString(-9));
// -> 11111111 11111111 11111111 11110111
Right shift (unsigned) (>>>)
Shifts the given number of bits to the right, adding 0s when adding bits in from the left, no matter what the sign is.
const n = 17;
const result = n >>> 1; // 8
console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001
console.log(createBinaryString(8));
// -> 00000000 00000000 00000000 00001000
const n = 17;
const result = n >>> 1; // 8
console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001
console.log(createBinaryString(8));
// -> 00000000 00000000 00000000 00001000
const n = -17;
const result = n >>> 1; // 2147483639
console.log(createBinaryString(-17));
// -> 11111111 11111111 11111111 11101111
console.log(createBinaryString(2147483639));
// -> 01111111 11111111 11111111 11110111
const n = -17;
const result = n >>> 1; // 2147483639
console.log(createBinaryString(-17));
// -> 11111111 11111111 11111111 11101111
console.log(createBinaryString(2147483639));
// -> 01111111 11111111 11111111 11110111
Getting a bit
To get a specific bit, we first need to create a bitmask.
We can do this by shifting 1 to the left by the index of the bit we want to get.
The result is the and of the binary number and the bitmask.
However, using JavaScript, we can also do an unsigned right shift by the index to put the bit in the first place (so that we don't get the actual value that is in that position, but whether it is a 1 or a 0):
function getBit(number, idx) {
const bitMask = 1 << idx;
const result = number & bitMask;
return result >>> idx;
}
function getBit(number, idx) {
const bitMask = 1 << idx;
const result = number & bitMask;
return result >>> idx;
}
For example, let's try 13, which is 1101 in binary:
const binaryNumber = 0b1101;
console.log('Bit at position 0:', getBit(binaryNumber, 0));
console.log('Bit at position 1:', getBit(binaryNumber, 1));
console.log('Bit at position 2:', getBit(binaryNumber, 2));
console.log('Bit at position 3:', getBit(binaryNumber, 3));
/*
Output:
Bit at position 0: 1
Bit at position 1: 0
Bit at position 2: 1
Bit at position 3: 1
*/
const binaryNumber = 0b1101;
console.log('Bit at position 0:', getBit(binaryNumber, 0));
console.log('Bit at position 1:', getBit(binaryNumber, 1));
console.log('Bit at position 2:', getBit(binaryNumber, 2));
console.log('Bit at position 3:', getBit(binaryNumber, 3));
/*
Output:
Bit at position 0: 1
Bit at position 1: 0
Bit at position 2: 1
Bit at position 3: 1
*/
Setting a bit
If we want to turn a bit to 1 (in other words, to "set a bit"), we can do a similar thing.
First, we can create a bitmask again by shifting 1 to the left by the index of the bit we want to set to 1.
The result is the or of the number and the bitmask:
function setBit(number, idx) {
const bitMask = 1 << idx;
return number | bitMask;
}
function setBit(number, idx) {
const bitMask = 1 << idx;
return number | bitMask;
}
Remember that in our example 13 was 1101 in binary, let's say we want to set the 0 at index 1:
const binaryNumber = 0b1101;
const newBinaryNumber = setBit(binaryNumber, 1);
console.log(createBinaryString(newBinaryNumber));
// -> 00000000 00000000 00000000 00001111
console.log('Bit at position 1:', getBit(newBinaryNumber, 1));
// -> Bit at position 1: 1
const binaryNumber = 0b1101;
const newBinaryNumber = setBit(binaryNumber, 1);
console.log(createBinaryString(newBinaryNumber));
// -> 00000000 00000000 00000000 00001111
console.log('Bit at position 1:', getBit(newBinaryNumber, 1));
// -> Bit at position 1: 1
We briefly looked at bitwise operations, as well as getting/setting a bit. In this final chapter, we will take a look at five problems, starting with Number of 1 Bits. Until then, happy coding.