20 · БИТЫ

Битовые операции

XOR, маски и сдвиги компактно представляют множества и двоичные состояния.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

a & b   // AND
a | b   // OR
a ^ b   // XOR
a << k  // shift

В Go ^x — битовое отрицание, а x ^ y — XOR.

mask |= 1 << bit
has := mask&(1<<bit) != 0
mask &^= 1 << bit

&^ — AND NOT, удобен для очистки бита.

ПРАКТИКА

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Пары взаимно уничтожаются через XOR.

O(n) time · O(1) space

solution.go

func singleNumber(nums []int) int {
    answer := 0
    for _, n := range nums { answer ^= n }
    return answer
}

ПРИМЕР РЕШЕНИЯ

n & (n−1) удаляет младшую единицу.

O(number of set bits) time · O(1) space

solution.go

func hammingWeight(n uint32) int {
    count := 0
    for n != 0 {
        n &= n - 1
        count++
    }
    return count
}

ПРИМЕР РЕШЕНИЯ

У степени двойки установлен ровно один бит.

O(1) time · O(1) space

solution.go

func isPowerOfTwo(n int) bool {
    return n > 0 && n&(n-1) == 0
}

ПЕРЕД КОДОМ