Na programação, podemos trabalhar com bits de forma eficaz. Primeiro, vamos ver as definições de cada operação de bit e depois passar para diferentes técnicas para resolver os problemas. Basicamente, existem seis operadores que cada linguagem suporta para manipulação de bits: &(AND), |(OR), ^(XOR), <<(deslocamento para a esquerda), >>(deslocamento para a direita) e ~(complemento).

Fatos sobre programação bit a bit

E bit a bit

O bit a bit AND testa dois números binários e retorna valores de bit de 1 para posições onde ambos os números têm um e valores de bit de 0 onde ambos os números não têm um.

// a = 10 (in binary)
var a = 2
// b = 11 (in binary)
var b = 3
// a & b = 10 & 11 = 10 (in binary) = 2 (in decimal)
a & b
<< 2

O bit a bit OR testa dois números binários e retorna valores de bit de 1 para posições em que um ou ambos os bits são um, o resultado de 0 só acontece quando ambos os bits são 0.

// a | b = 10 | 11 = 11 (in binary) = 3(in decimal)
a | b
<< 3

O XOR bit a bit testa dois números binários e retorna valores de bit de 1 para posições em que ambos os bits são diferentes; se forem iguais, o resultado é 0.

// a ^ b = 10 ^ 11 = 01 (in binay) = 1 (in decimal)
a ^ b
<< 1

O deslocamento para a esquerda bit a bit move todos os bits no número para a esquerda e preenche as posições de bit vagas com 0 (deslocamento para a esquerda) ou 1 (deslocamento para a esquerda sem sinal).

// c = 0101 (in binary)
var c = 5
// bitwise left shift: c << 1 = 1010 (in binary) = 10 (in decimal)
c << 1
<< 1

O deslocamento para a direita bit a bit move todos os bits do número para a direita.

// c >> 1 = 010 (in binary) = 2 (in decimal)
c >> 1
<< 2

O complemento bit a bit inverte os bits em um único número binário.

// ~c -> 1010 (in binary) -> 10 (in decimal), 2’s compliment of 10 will be -6.
~c
<< -6

Verificar se o número é potência de 2 ou não

Determinado número n, para verificar se o número está em 2^nforma para não, podemos usar a expressão: if(n & n — 1 == 0).

// n = 10000
var n = 16 // 2⁴
// n — 1 = 15 (in decimal) = 01111
// n & (n — 1) = 10000 & 01111 = 0
n & (n — 1)
<< 0

Para um determinado número n, para multiplicar o número com 2^kque podemos usar a expressão: n ≪ k.

var n = 16
// 16*(2^1) = 32
n << 1
<< 32

Para um determinado número n, dividir o número com 2^kque podemos usar a expressão: n ≫ k.

var n = 16
// 16/(2²) = 4
n >> 2
<< 4

Existe um algoritmo de ajuste de bits para substituir mid = (low + high) / 2(usado na pesquisa binária e classificação de mesclagem) por algo muito mais rápido?

Podemos usar mid = (low + high) >> 1.

Encontrando o Módulo de um Número Fornecido

Para um determinado número n, para encontrar o %8que podemos usar a expressão: n & 0x7. Da mesma forma, para encontrar %32, usar a expressão: n & 0x1F.

var n = 20
// 20%8 = 4
n & 0x7
<< 4

Verificar se K-th bit está definido ou não

Suponhamos que o número fornecido seja n. Em seguida, para verificar o K-thpouco que podemos usar a expressão: n & (1 ≪ K 1). Se a expressão for verdadeira, podemos dizer que o K-th bit está definido (ou seja, definido como 1).

// n = 01001011 (in binary)
var n = 75
var k = 4
// 1 << k — 1 = 00001000 (in binary)
// n & (1 << k — 1) = 01001011 & 00001000 = 00001000 = 8 (in decimal)
n & (1 << k — 1)
<< 8

Para um determinado número n, para definir o K-thbit podemos usar a expressão: n | 1 ≪ (K — 1). Suponha que precisamos definir o terceiro bit de n.

// n = 01001011 (in binary)
var n = 75
var k = 3
// 1 << k — 1 = 00000100 (in binary)
// n | (1 << k — 1) = 01001011 | 00000100 = 01001111 (in binary) = 79 (in decimal)
n | (1 << k — 1)
<< 79

Para limpar K-thbit de um determinado número n, podemos usar a expressão: n & ~(1 ≪ K — 1).

// n = 01001011 (in binary)
var n = 75
var k = 3
// 1 << k — 1 = 00000100 (in binary)
// n & (1 << k — 1) = 01001011 & 00000100 = 0 (in binary) = 0 (in decimal)
n & (1 << k — 1)
<< 0

Para um determinado número n, se k-thbit for 0, alterne para 1e, se for 1, alterne para 0. Podemos usar a expressão: n ^(1 ≪ k –1).

// n = 01001011 (in binary) -> toggle(n, k) = 01001111
var n = 75
var k = 3
// 1 << k — 1 = 00000100 (in binary)
// n ^ (1 << k — 1) = 01001011 ^ 00000100 = 01001111 (in binary) = 79 (in decimal)
n ^ (1 << k — 1)
<< 79

Para um determinado número n, para alternar mais à direita mordeu podemos usar a expressão: n & n — 1.

// n = 01001011 (in binary)
var n = 75
// n — 1 = 74 = 01001010
// n & n — 1 = 01001011 & 01001010 = 01001010 = 74
n & n — 1
<< 74