LeetCode Meditations — Chapter Bit Manipulation

Table of contents

• Introduction
• Bitwise operators
  • AND (&)
  • OR (|)
  • XOR (^)
  • NOT (~)
  • Left shift (zero fill) (<<)
  • Right shift (sign preserving) (>>)
  • Right shift (unsigned) (>>>)
• Getting a bit
• Setting a bit
• Resources

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

We can also parse an integer giving it a base:

console.log(parseInt(10001, 2)); // 17

Note that we can also represent a binary number with the prefix 0b:

console.log(0b10001); // 17
console.log(0b101); // 5

For example, these are the same number:

0b1 === 0b00000001 // true

---

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.

Note

The GIFs below show the numbers as 8-bit strings, but when doing bitwise operations, remember they are converted to 32-bit numbers.

const n = 17;

console.log(n.toString(2)); // 10001

OR (|)

If either of the bits is 1, the result is 1, otherwise 0.

console.log(parseInt(10001, 2)); // 17

XOR (^)

If the bits are different (one is 1 and the other is 0), the result is 1, otherwise 0.

console.log(0b10001); // 17
console.log(0b101); // 5

NOT (~)

Flips the bits (1 becomes 0, 0 becomes 1).

0b1 === 0b00000001 // true

Note

Bitwise NOTing any 32-bit integer x yields -(x 1).

If we use a helper function to see the binary representations, it is as we expected:

const n = 17;

console.log(n.toString(2)); // 10001

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.

Note that two's complement allows us to get a number with an inverse signal.
One way to do it is to invert the bits of the number in the positive representation and add 1 to it:

console.log(parseInt(10001, 2)); // 17

Left shift (zero fill) (<<)

Shifts the given number of bits to the left, adding zero bits shifted in from the right.

console.log(0b10001); // 17
console.log(0b101); // 5

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.

0b1 === 0b00000001 // true

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 & x2; // 1 (0b1)

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 x1 = 0b10001;
const x2 = 0b101;

const result = x1 | x2; // 21 (0b10101)

const x1 = 0b10001;
const x2 = 0b101;

const result = x1 ^ x2; // 20 (0b10100)

---

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):

const n = 17;

const result = ~n; // -18

For example, let's try 13, which is 1101 in binary:

console.log(createBinaryString(n));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(result));
// -> 11111111 11111111 11111111 11101110

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 twosComplement(n) {
  return ~n + 0b1;
}

Remember that in our example 13 was 1101 in binary, let's say we want to set the 0 at index 1:

const n = 17;
const result = n << 1; // 34


console.log(createBinaryString(17));
// -> 00000000 00000000 00000000 00010001

console.log(createBinaryString(34));
// -> 00000000 00000000 00000000 00100010

---

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.

Resources

• "The Absolute Essentials for Bit Manipulation in JavaScript" - Lucas F. Costa
• JS Bitwise Operators
• Number (MDN)
• Bitwise AND (MDN)
• Bitwise NOT (MDN)
• Bitwise OR (MDN)
• Bitwise XOR (MDN)
• Left shift (MDN)
• Right shift (MDN)
• Unsigned right shift (MDN)

The above is the detailed content of LeetCode Meditations — Chapter Bit Manipulation. For more information, please follow other related articles on the PHP Chinese website!