Bitwise Algorithms Basics

Bitwise algorithms are used to perform operations at the bit-level or to manipulate bits in different ways. Bitwise operations are extremely fast because they are executed directly by the CPU, making them a powerful tool to optimize program efficiency.

For example, to check if a number is even or odd, we can use the Bitwise-AND (&) operator. If the last bit of the number is set, the number is odd; otherwise, it is even. Therefore, if (num & 1) !== 0 then num is odd, otherwise it is even.

Bitwise Operators

Bitwise operators work on the binary representations of numbers (which are treated as 32-bit signed integers in JavaScript during bitwise operations). Below is a summary of the six types of bitwise operators:

Here, we will cover the first three operators in detail.

Core Operators Deep Dive

1. Bitwise AND (&)

• Symbol: & (Typed using Shift + 7)
• Output: 1 only if both bits are 1, otherwise 0.

Truth Table

Example

let x = 2; // Binary: 00000000000000000000000000000010
let y = 6; // Binary: 00000000000000000000000000000110
 
console.log(x & y); // Output: 2 (Binary: 00000000000000000000000000000010)

Only the second bit is set in both numbers, hence the result is 2.

2. Bitwise OR (|)

• Symbol: | (Typed using Shift + \)
• Output: 1 if at least one bit is 1, otherwise 0.

Truth Table

Example

let x = 2; // Binary: 00000000000000000000000000000010
let y = 6; // Binary: 00000000000000000000000000000110
 
console.log(x | y); // Output: 6 (Binary: 00000000000000000000000000000110)

Any bit that is 1 in either number becomes 1 in the result.

3. Bitwise XOR (^)

• Symbol: ^ (Typed using Shift + 6)
• Output: 1 only if the two bits are different, otherwise 0.

Truth Table

Example

let x = 2; // Binary: 00000000000000000000000000000010
let y = 6; // Binary: 00000000000000000000000000000110
 
console.log(x ^ y); // Output: 4 (Binary: 00000000000000000000000000000100)

Bits that differ remain set in the result.

Important Facts about Bitwise Operators

• Shift Limit with Negatives: The left-shift (<<) and right-shift (>>) operators cannot be used with negative numbers in standard bitwise contexts, as shifting negative numbers behaves differently due to the sign bit.
• XOR's Interview Prominence: The bitwise XOR operator is the most useful operator from a technical interview perspective because of its unique properties (e.g. x ^ x = 0 and x ^ 0 = x). We will see some very useful applications of the XOR operator later in the course.
• Do Not Substitute Logical Operators: Bitwise operators should not be used in place of logical operators (&&, ||, !) because they do not perform short-circuit evaluation and operate on numbers rather than booleans.
• Powers of 2 Equivalence: The left-shift (<<) and right-shift (>>) operators are equivalent to multiplication and division by powers of 2 respectively:
  • x << y is equivalent to x * 2^y.
  • x >> y is equivalent to Math.floor(x / 2^y).
• Even/Odd Verification: The & operator can be used to quickly check if a number is odd or even. The value of expression (x & 1) is non-zero (specifically 1) only if x is odd; otherwise, the value is 0.