Một số mẹo thao tác bit hay hỏi: kiểm tra lũy thừa của 2, đếm số bit 1, đổi chỗ không cần biến tạm — giải thích cơ chế?

Vài mánh cốt lõi:

• Lũy thừa của 2: n > 0 && (n & (n - 1)) === 0. Lũy thừa của 2 chỉ có đúng 1 bit bật; n - 1 lật bit đó và mọi bit thấp hơn → AND ra 0.
• Đếm bit 1 (Brian Kernighan): n &= n - 1 xóa bit 1 thấp nhất mỗi vòng → lặp đúng bằng số bit 1, nhanh hơn quét 32 bit.
• XOR tìm phần tử lẻ: a ^ a = 0, a ^ 0 = a → XOR cả mảng để lọc số xuất hiện lẻ lần (bài Single Number).
• Đổi chỗ không biến tạm: a ^= b; b ^= a; a ^= b.
• Bit thứ i: lấy (n >> i) & 1; bật n | (1 << i); tắt n & ~(1 << i).

const isPowerOfTwo = (n: number) => n > 0 && (n & (n - 1)) === 0

function hammingWeight(n: number): number {
  let count = 0
  while (n !== 0) { n &= n - 1; count++ } // xóa bit 1 thấp nhất
  return count
}

function singleNumber(nums: number[]): number {
  return nums.reduce((acc, x) => acc ^ x, 0)
}

Độ phức tạp: đếm bit O(số bit 1); XOR mảng O(n) thời gian, O(1) bộ nhớ.

Lưu ý: Trong JS, toán tử bit chạy trên int 32-bit có dấu — số lớn hơn 2³¹ sẽ sai; cần >>> 0 hoặc BigInt.

Core tricks:

• Power of two: n > 0 && (n & (n - 1)) === 0. A power of two has exactly one set bit; n - 1 flips that bit and all lower ones → AND is 0.
• Count set bits (Brian Kernighan): n &= n - 1 clears the lowest set bit each loop → iterates exactly as many times as there are 1-bits, faster than scanning 32 bits.
• XOR to find the odd one: a ^ a = 0, a ^ 0 = a → XOR the whole array to isolate the value appearing an odd number of times (Single Number).
• Swap without a temp: a ^= b; b ^= a; a ^= b.
• i-th bit: read (n >> i) & 1; set n | (1 << i); clear n & ~(1 << i).

const isPowerOfTwo = (n: number) => n > 0 && (n & (n - 1)) === 0

function hammingWeight(n: number): number {
  let count = 0
  while (n !== 0) { n &= n - 1; count++ } // clear lowest set bit
  return count
}

function singleNumber(nums: number[]): number {
  return nums.reduce((acc, x) => acc ^ x, 0)
}

Complexity: counting bits O(#set bits); XOR over array O(n) time, O(1) space.

Note: In JS, bitwise operators run on signed 32-bit ints — values above 2³¹ break; use >>> 0 or BigInt.