0Pricing
Coding Interview Prep · Aula

Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos

Revise os seis operadores bit a bit com tabelas-verdade e exemplos em Python e entenda como os deslocamentos à esquerda e à direita se relacionam à multiplicação e à divisão por dois.

Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.

Por que a manipulação de bits é importante

A manipulação de bits permite operar diretamente sobre a representação binária de inteiros. Muitos problemas que parecem complexos tornam-se triviais com o truque bit a bit correto: encontrar um número ausente em O(n) de tempo e O(1) de espaço, trocar variáveis sem uma variável temporária ou codificar subconjuntos de forma compacta. Entrevistadores usam esses problemas para avaliar a compreensão de baixo nível e o pensamento criativo.

Os inteiros do Python têm precisão arbitrária — podem ser tão grandes quanto a memória permitir —, mas as operações de bits sempre seguem a semântica padrão do complemento de dois no nível do hardware. Todos os seis operadores trabalham bit a bit sobre as representações binárias dos inteiros.

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

Operador AND: mascaramento de bits

O operador AND (&) produz 1 somente quando ambos os bits de entrada são 1. Seu principal uso é o mascaramento: selecionar bits específicos de um número enquanto zera todos os demais. Para verificar se o bit k está definido no número n, avalie n & (1 << k) — se o resultado for diferente de zero, o bit k vale 1.

AND também é usado para limpar o bit definido mais à direita: n & (n - 1) remove o bit 1 mais à direita. Isso é usado para contar bits definidos de maneira eficiente e para verificar se um número é uma potência de dois (uma potência de dois tem exatamente um bit definido, portanto n & (n-1) == 0).

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

Operador OR: definição de bits

O operador OR (|) produz 1 se pelo menos um dos bits de entrada for 1. Seu principal uso é definir um bit específico como 1 sem afetar os demais. Para definir o bit k no número n, use n | (1 << k). O 1 deslocado para a posição k ativa esse bit; todos os outros permanecem inalterados, porque qualquer valor submetido a OR com 0 permanece igual.

OR também é usado para combinar sinalizadores: se você representar sinalizadores de recursos como bits individuais, poderá habilitar vários sinalizadores com OR. Por exemplo, READ | WRITE | EXECUTE combina três bits de permissão em um único inteiro.

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

Operador XOR: alternância e diferença

O operador XOR (^) produz 1 quando os bits de entrada são diferentes. XOR tem três propriedades algébricas importantes: a ^ a = 0 (entradas iguais se anulam), a ^ 0 = a (zero é o elemento neutro) e XOR é ao mesmo tempo comutativo e associativo. Essas propriedades fazem de XOR a ferramenta ideal para encontrar elementos únicos.

XOR também é usado para alternar um bit específico: n ^ (1 << k) inverte o bit k e mantém os demais inalterados. Se o bit k era 0, ele se torna 1; se era 1, torna-se 0.

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

Operador NOT e complemento de dois

O operador NOT (~) inverte todos os bits. Em Python, ~n é igual a -(n+1) devido à representação em complemento de dois. Isso surpreende muitas pessoas: ~5 = -6, e não o valor 0b11111010 que seria esperado de maneira ingênua. Os inteiros do Python têm precisão infinita, portanto inverter todos os bits de um número positivo produz um resultado negativo em complemento de dois.

Na prática, raramente se usa ~ sozinho em Python para manipulação de bits. Em vez disso, use-o em combinação com AND para limpar bits específicos ou calcule ~n & mask, em que mask limita a largura a uma quantidade específica de bits (por exemplo, & 0xFFFFFFFF para 32 bits).

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

Deslocamento à esquerda: multiplicação por potências de dois

O operador de deslocamento à esquerda (<<) desloca todos os bits para a esquerda em k posições, preenchendo as posições desocupadas à direita com zeros. Isso equivale a multiplicar por 2^k. Deslocar 1 posição à esquerda dobra o valor; deslocar k posições à esquerda multiplica por 2^k.

Em problemas de entrevistas, deslocamentos à esquerda são usados principalmente para criar máscaras de bits: 1 << k cria um número com apenas o bit k definido. Essa é a base de todas as operações de manipulação de bits — definir, limpar, alternar e verificar bits individuais começa com 1 << k.

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

Deslocamento à direita: divisão por potências de dois

O operador de deslocamento à direita (>>) desloca todos os bits para a direita em k posições, descartando os k bits mais à direita. Isso equivale à divisão inteira por 2^k. O deslocamento à direita do Python é sempre aritmético: os bits mais à esquerda são preenchidos com o bit de sinal (0 para valores positivos, 1 para valores negativos).

Um truque comum em entrevistas: para extrair o bit k do número n, use (n >> k) & 1. Isso desloca o bit k para a posição 0 e mascara todos os outros bits. É a maneira mais simples de verificar qualquer bit específico sem precisar calcular e comparar uma máscara completa.

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

Folha de consulta de truques práticos com bits

Aqui está uma coleção dos padrões idiomáticos mais comuns de manipulação de bits que você encontrará em entrevistas. Memorize estes padrões — eles aparecem repetidamente em dezenas de problemas:

  • n & 1 — verificar se n é ímpar
  • n & (n-1) — limpar o bit definido mais baixo
  • n & -n — isolar o bit definido mais baixo
  • n | (1 << k) — definir o bit k
  • n & ~(1 << k) — limpar o bit k
  • n ^ (1 << k) — alternar o bit k
  • (n >> k) & 1 — verificar o bit k
# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

Contagem de bits definidos (contagem populacional)

Contar o número de bits 1 em um inteiro é chamado de contagem populacional (popcount). A abordagem ingênua percorre todos os bits. O truque de Brian Kernighan é mais rápido: limpe repetidamente o bit definido mais baixo com n &= n - 1, contando as iterações até n se tornar 0. Cada iteração remove exatamente um bit 1, portanto o laço executa exatamente tantas vezes quanto o número de bits 1.

O Python 3.10+ fornece int.bit_count(), que retorna a contagem diretamente. Em versões mais antigas, o truque de Kernighan é a abordagem manual padrão. Essa técnica também resolve o problema 'Peso de Hamming' no LeetCode.

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

Manipulação de bits em Python: armadilhas importantes

Ao contrário de C/Java, os inteiros do Python são arbitrariamente grandes — não há estouro de 32 ou 64 bits. Isso significa que você precisa mascarar manualmente os resultados para uma largura fixa ao resolver problemas que esperam comportamento de 32 bits: use & 0xFFFFFFFF para manter apenas os 32 bits inferiores.

O operador NOT ~n em Python retorna -(n+1), e não a versão com os bits invertidos que você poderia esperar de C. Para problemas de 32 bits, use ~n & 0xFFFFFFFF ou calcule 0xFFFFFFFF ^ n para obter o complemento de 32 bits esperado. Essas diferenças confundem muitos candidatos acostumados à manipulação de bits no estilo de C.

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

Operadores de deslocamento e multiplicação

Os deslocamentos à esquerda e à direita oferecem uma maneira extremamente rápida de multiplicar ou dividir por potências de dois. No hardware, os deslocamentos de bits são operações de uma única instrução, enquanto a multiplicação e a divisão exigem vários ciclos. Em Python, a multiplicação de inteiros já é eficiente, mas entender essa relação ajuda você a visualizar os padrões de bits com mais clareza.

Uma identidade útil: para verificar se n é múltiplo de 2^k, use (n & (2^k - 1)) == 0. A máscara 2^k - 1 tem todos os k bits inferiores definidos como 1; aplicar AND a ela fornece o resto da divisão por 2^k. Isso equivale a n % (2^k), mas é mais rápido em linguagens baseadas em C.

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

Verificação rápida

Verifique sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação apresentados nesta lição.

Recapitulação da lição

Nesta lição, você aprendeu que: AND mascara bits, OR define bits, XOR alterna bits e detecta diferenças, NOT inverte bits (produz -(n+1) em Python) e os deslocamentos multiplicam/dividem por potências de dois, n & (n-1) limpa o bit definido mais baixo e serve de base para verificações de potências de dois e contagem de bits e o Python não tem estouro de largura fixa, portanto problemas de 32 bits exigem mascaramento explícito com & 0xFFFFFFFF. A seguir, exploraremos a propriedade de auto-inversão de XOR para resolver a família de problemas do número único.

Perguntas Frequentes

A aula “Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos” é grátis?

Sim — o texto completo de “Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.

O que vou aprender em “Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos”?

Revise os seis operadores bit a bit com tabelas-verdade e exemplos em Python e entenda como os deslocamentos à esquerda e à direita se relacionam à multiplicação e à divisão por dois. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Coding Interview Prep?

Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.

Quanto tempo leva a aula “Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Coding Interview Prep?

Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

  1. Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos
  2. Número único e propriedades de XOR
  3. Máscaras de bits: definir, limpar, alternar e verificar
  4. Contagem de bits, número ausente e inversão de bits
← Voltar para Coding Interview Prep