LeetCode Meditations — Chapter 14: 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.

, 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.

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 n = 17;



const result = ~n; // -18

If we use . 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:

function twosComplement(n) {

  return ~n + 0b1;

}

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

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; // -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; // 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;

}

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

*/

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;    

}

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

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