Máscaras de bits: definir, limpar, alternar e verificar
Implemente funções auxiliares para definir, limpar, alternar e verificar bits individuais e aplique máscaras de bits para representar subconjuntos em problemas de enumeração de subconjuntos.
Máscaras de bits: definir, limpar, alternar e verificar é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 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.
O que são máscaras de bits
Uma máscara de bits é um inteiro usado para selecionar, modificar ou testar bits específicos em outro inteiro. A máscara contém 1 nas posições relevantes e 0 nas demais. Combinadas com operadores bit a bit, as máscaras permitem realizar operações detalhadas nos bits sem afetar os outros.
As quatro operações fundamentais com máscaras são: definir (ativar um bit), limpar (desativar um bit), alternar (inverter um bit) e verificar (testar se um bit é 1). Cada uma usa um operador diferente — OR, AND com NOT, XOR e AND, respectivamente — com a máscara 1 << k.
# The four fundamental bit mask operations
def set_bit(n, k): return n | (1 << k) # OR to set
def clear_bit(n, k): return n & ~(1 << k) # AND-NOT to clear
def toggle_bit(n, k): return n ^ (1 << k) # XOR to toggle
def check_bit(n, k): return (n >> k) & 1 # shift+AND to check
n = 0b10110101 # 181
print(f'n = {bin(n)}')
print(f'set bit 1: {bin(set_bit(n, 1))}')
print(f'clear bit 2: {bin(clear_bit(n, 2))}')
print(f'toggle bit 0: {bin(toggle_bit(n, 0))}')
print(f'check bit 4: {check_bit(n, 4)}')Definir um bit: ativando um bit
Para definir o bit k (forçá-lo a 1, independentemente do valor atual), aplique OR ao número com a máscara 1 << k. Como 0 OR 1 = 1 e 1 OR 1 = 1, o bit-alvo se torna 1. A operação OR com 0 em todos os demais bits não os altera.
Definir um bit é uma operação idempotente — chamá-la várias vezes produz o mesmo efeito que chamá-la uma única vez. Se o bit k já for 1, o resultado não muda. Essa propriedade é importante no gerenciamento de sinalizadores, quando você deseja ativar um recurso sem se preocupar com seu estado atual.
def set_bit(n, k):
mask = 1 << k
return n | mask
# Set various bits
n = 0b00001010 # 10
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = set_bit(n, k)
print(f'Set bit {k}: {bin(result)} = {result}')
# Idempotence: setting already-set bit does nothing
n = 0b1111
print(f'\nAlready set: {bin(set_bit(n, 2))} = {bin(n)} (unchanged)')
# Setting multiple bits at once with a combined mask
mask = (1 << 0) | (1 << 2) | (1 << 4) # bits 0, 2, 4
print(f'Set bits 0,2,4: {bin(0 | mask)} = {0 | mask}')Limpar um bit: desativando um bit
Para limpar o bit k (forçá-lo a 0, independentemente do valor atual), aplique AND ao número com o complemento da máscara: n & ~(1 << k). O complemento ~(1 << k) tem todos os bits definidos como 1, exceto o bit k, que vale 0. Aplicar AND com 0 força o bit-alvo a 0; aplicar AND com 1 preserva todos os demais bits.
Assim como definir, limpar é uma operação idempotente. Limpar um bit que já vale 0 não altera o número. Em Python, ~(1 << k) funciona corretamente para qualquer k porque Python trata automaticamente a extensão de sinal — conceitualmente, o complemento tem todos os bits superiores definidos como 1.
def clear_bit(n, k):
mask = ~(1 << k) # all 1s except bit k
return n & mask
n = 0b11111111 # 255: all bits set
print(f'Original: {bin(n)} = {n}')
for k in [0, 3, 6, 7]:
result = clear_bit(n, k)
print(f'Clear bit {k}: {bin(result)} = {result}')
# Clear multiple bits with combined mask complement
def clear_bits(n, positions):
mask = 0
for k in positions:
mask |= (1 << k)
return n & ~mask
result = clear_bits(0b11111111, [1, 3, 5, 7])
print(f'Clear bits 1,3,5,7: {bin(result)} = {result}') # 0b01010101 = 85Alternar um bit: invertendo um bit
Para alternar o bit k (invertê-lo de 0 para 1 ou de 1 para 0), aplique XOR ao número com a máscara 1 << k. XOR com 1 inverte o bit; XOR com 0 não o altera. Essa é a propriedade fundamental de XOR aplicada a um único bit.
Alternar é a única das quatro operações que não é idempotente — chamá-la duas vezes faz o valor voltar ao original. Isso a torna ideal para recursos que alternam entre dois estados, como uma chave liga/desliga ou um sinalizador booleano em uma representação inteira compacta.
def toggle_bit(n, k):
return n ^ (1 << k)
n = 0b10101010 # 170
print(f'Original: {bin(n)}')
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}') # off->on: 10101011
print(f'Toggle bit 1: {bin(toggle_bit(n, 1))}') # on->off: 10101000
print(f'Toggle bit 7: {bin(toggle_bit(n, 7))}') # on->off: 00101010
# Toggle is its own inverse: two toggles = no change
result = toggle_bit(toggle_bit(n, 3), 3)
print(f'Double toggle bit 3: {bin(result)} == original {bin(n)}? {result == n}')
# Toggle all lower k bits
def toggle_lower_k(n, k):
mask = (1 << k) - 1 # k ones in the lowest positions
return n ^ mask
print(f'Toggle lower 4 bits of {bin(n)}: {bin(toggle_lower_k(n, 4))}')Verificar um bit: testando se um bit está definido
Para verificar se o bit k está definido, desloque n para a direita em k posições e aplique AND com 1: (n >> k) & 1. Isso traz o bit k para a posição 0 e mascara todos os bits superiores, deixando 0 (o bit k era 0) ou 1 (o bit k era 1). Como alternativa, use bool(n & (1 << k)) para obter um resultado Verdadeiro/Falso.
Verificar um bit não altera o valor — n permanece intacto. Você pode verificar vários bits deslocando e aplicando a máscara a cada posição de forma independente. Essa é a base para percorrer a representação binária de um número, algo usado na enumeração de subconjuntos e na programação dinâmica com estados de máscaras de bits.
def check_bit(n, k):
return (n >> k) & 1
def is_bit_set(n, k):
return bool(n & (1 << k))
n = 0b10110101 # 181
print(f'n = {bin(n)} = {n}')
for k in range(8):
print(f'Bit {k}: {check_bit(n, k)} ({"set" if check_bit(n, k) else "clear"})')
# Count set bits using check_bit
def count_set_bits(n):
return sum(check_bit(n, k) for k in range(n.bit_length()))
print(f'\nSet bits in {n}: {count_set_bits(n)}')
# Get bit representation as list (LSB first)
def to_bit_list(n, width=8):
return [check_bit(n, k) for k in range(width)]
print(f'Bit list (LSB first): {to_bit_list(n)}')Máscaras de bits para representar subconjuntos
Um inteiro com n bits pode representar um subconjunto de um conjunto com n elementos: o bit k vale 1 se o elemento k estiver no subconjunto e 0 caso contrário. Isso compacta um subconjunto em um único inteiro, permitindo operações O(1): teste de pertinência (mask & (1 << k)), adição de um elemento (mask | (1 << k)), remoção de um elemento (mask & ~(1 << k)) e união/interseção de conjuntos (mask1 | mask2 e mask1 & mask2).
Com n elementos, existem 2^n subconjuntos possíveis, cada um representado de forma única por um inteiro de n bits entre 0 e 2^n - 1. Percorrer todos os inteiros de 0 a 2^n - 1 enumera todos os subconjuntos.
# Subset representation with bitmasks
elements = ['A', 'B', 'C', 'D']
n = len(elements)
def subset_from_mask(mask):
return [elements[k] for k in range(n) if (mask >> k) & 1]
# Enumerate all 2^n subsets
print('All subsets:')
for mask in range(1 << n): # 0 to 15 for n=4
print(f' {mask:04b}: {subset_from_mask(mask)}')
# Set operations
mask_ab = 0b0011 # {A, B}
mask_bc = 0b0110 # {B, C}
print(f'\nUnion: {subset_from_mask(mask_ab | mask_bc)}')
print(f'Intersection: {subset_from_mask(mask_ab & mask_bc)}')
print(f'Difference A\\B: {subset_from_mask(mask_ab & ~mask_bc & 0b1111)}')Percorrendo todos os subconjuntos de uma máscara
Na programação dinâmica com máscaras de bits, frequentemente é necessário percorrer todos os subconjuntos de uma determinada máscara. Um truque comum é começar com sub = mask e repetir sub = (sub - 1) & mask até sub chegar a 0. Cada iteração produz uma submáscara diferente. O custo total para todas as máscaras é O(3^n), pois cada elemento pode estar na máscara externa, mas não na submáscara, em ambas ou em nenhuma.
Essa técnica aparece em problemas como “particionar um vetor em subconjuntos com XOR igual” ou “encontrar o maior AND de qualquer subconjunto”. A capacidade de enumerar submáscaras com eficiência é uma característica marcante da programação dinâmica avançada com máscaras de bits.
def all_submasks(mask):
submasks = []
sub = mask
while sub > 0:
submasks.append(sub)
sub = (sub - 1) & mask
submasks.append(0) # empty subset
return submasks
mask = 0b1011 # {0, 1, 3}
elements = ['A', 'B', 'C', 'D']
def show(m): return '{' + ','.join(elements[k] for k in range(4) if (m>>k)&1) + '}'
print(f'All submasks of {bin(mask)} = {show(mask)}:')
for sub in all_submasks(mask):
print(f' {bin(sub):6s}: {show(sub)}')
print(f'Total: {len(all_submasks(mask))} submasks (should be 2^{bin(mask).count("1")} = {2**bin(mask).count("1")})')DP com Máscara de Bits: Visão Geral do Caixeiro-viajante
DP com máscara de bits resolve problemas nos quais the estado inclui um subconjunto de itens visitados. O exemplo clássico é o Problema do Caixeiro-viajante (TSP): encontre o percurso de custo mínimo que visite n cidades. O estado é dp[mask][city] = custo mínimo para visitar the cidades em mask, terminando em city. Com n cidades, há 2^n × n estados, resultando em tempo O(n^2 × 2^n) — viável para n ≤ 20.
A máscara funciona como um conjunto compactado de visitados. Definir, limpar e verificar bits corresponde a visitar, deixar e consultar cidades. Esse é o princípio central de DP com máscara de bits: usar bits como um conjunto compacto para representar the estado.
# TSP with bitmask DP
import sys
def tsp(dist):
n = len(dist)
INF = float('inf')
# dp[mask][v] = min cost to reach v having visited cities in mask
dp = [[INF] * n for _ in range(1 << n)]
dp[1][0] = 0 # start at city 0, only city 0 visited (mask=1=0b0001)
for mask in range(1 << n):
for v in range(n):
if dp[mask][v] == INF: continue
if not (mask >> v) & 1: continue # v must be in mask
for u in range(n):
if (mask >> u) & 1: continue # u must not be visited
new_mask = mask | (1 << u)
dp[new_mask][u] = min(dp[new_mask][u], dp[mask][v] + dist[v][u])
full_mask = (1 << n) - 1
return min(dp[full_mask][v] + dist[v][0] for v in range(1, n))
dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
print('TSP minimum tour cost:', tsp(dist)) # should be 80Mascaramento de Vários Bits: Extração de um Campo
Às vezes, você precisa extrair não apenas um bit individual, mas um campo de vários bits — um intervalo contíguo de bits. Para extrair bits da posição inicial até a posição inicial + comprimento - 1, crie uma máscara de length bits 1 consecutivos: mask = (1 << length) - 1 e, em seguida, use (n >> start) & mask.
Essa técnica é usada na análise de formatos de inteiros compactados, como endereços IP, dados de pixels ou registradores de componentes físicos, nos quais vários valores pequenos são armazenados em um único inteiro. Por exemplo, um pixel RGB565 de 16 bits armazena o vermelho nos bits 15-11, o verde nos bits 10-5 e o azul nos bits 4-0.
def extract_field(n, start, length):
mask = (1 << length) - 1 # e.g., length=3 => mask=0b111
return (n >> start) & mask
# RGB565 pixel format: RRRRRGGGGGGBBBBB
pixel = 0b1111100111001000 # 63432
red = extract_field(pixel, 11, 5) # bits 15-11
green = extract_field(pixel, 5, 6) # bits 10-5
blue = extract_field(pixel, 0, 5) # bits 4-0
print(f'Pixel: {hex(pixel)}')
print(f'Red: {red} ({bin(red)})')
print(f'Green: {green} ({bin(green)})')
print(f'Blue: {blue} ({bin(blue)})')
# Packing values back
def pack_rgb565(r, g, b):
return (r << 11) | (g << 5) | b
packe = pack_rgb565(red, green, blue)
print(f'Repacked: {hex(packed) if (packed := pack_rgb565(red,green,blue)) else 0}')Máscaras de Bits em Problemas de Entrevistas
As máscaras de bits aparecem com frequência nestes tipos de problemas de entrevistas:
- Enumeração de subconjuntos: percorra todos os 2^n subconjuntos usando máscaras de 0 a 2^n-1
- DP com compressão de estado: codifique um conjunto de nós ou itens visitados como uma máscara de bits no estado de DP
- Sistemas de permissões: combine os sinalizadores READ/WRITE/EXECUTE com OR e faça a verificação com AND
- Rastreamento de visitados em grades: em grades pequenas, armazene as células visitadas em um único inteiro
Um indício importante de que máscaras de bits são úteis: o problema envolve um conjunto pequeno (n ≤ 20 itens) e você precisa acompanhar combinações de pertencimento. Conjuntos maiores exigem representações diferentes.
# Subset sum with bitmask enumeration
def subset_sum_exists(nums, target):
n = len(nums)
for mask in range(1 << n):
total = sum(nums[k] for k in range(n) if (mask >> k) & 1)
if total == target:
subset = [nums[k] for k in range(n) if (mask >> k) & 1]
print(f'Found subset {subset} summing to {target}')
return True
return False
subset_sum_exists([3, 1, 4, 1, 5], 10) # finds a subset summing to 10
# Check if permutation covers all required elements (bitmask approach)
required = 0b11111 # need all 5 elements
visited = 0b01101 # visited elements 0, 2, 3
all_visited = (visited & required) == required
print(f'All required visited: {all_visited}') # False: missing bits 1 and 4Técnicas Eficientes de Enumeração de Bits
Ao percorrer os bits definidos de uma máscara, duas técnicas comuns são usadas. O método de deslocamento e verificação: desloque para a direita e verifique o LSB. O método de isolamento do bit 1 menos significativo: isole o bit 1 menos significativo com n & -n, processe-o e depois limpe-o com n &= n - 1. O segundo método visita apenas os bits definidos e é mais rápido quando a máscara é esparsa.
Em Python, você também pode usar bin(n).count('1') ou n.bit_count() (3.10 ou posterior) para contar bits 1. Para obter a posição de cada bit definido, use n.bit_length() - 1 para o bit definido mais alto.
# Iterate over set bit positions
def set_bit_positions(n):
positions = []
k = 0
while n:
if n & 1:
positions.append(k)
n >>= 1
k += 1
return positions
# Faster: use lowest-set-bit isolation
def set_bit_positions_fast(n):
positions = []
while n:
lsb = n & -n # isolate lowest set bit
k = lsb.bit_length() - 1 # position of that bit
positions.append(k)
n &= n - 1 # clear lowest set bit
return positions
mask = 0b10110101
print(f'Set positions (naive): {set_bit_positions(mask)}')
print(f'Set positions (fast): {set_bit_positions_fast(mask)}')
print(f'Bit count: {bin(mask).count("1")}')
print(f'Highest set bit: {mask.bit_length() - 1}')Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Resumo da Lição
Nesta lição, você aprendeu: the quatro operações fundamentais de máscaras de bits são definir (OR), limpar (AND-NOT), alternar (XOR) e verificar (deslocamento-AND); inteiros podem representar subconjuntos, nos quais cada bit codifica o pertencimento de um elemento, permitindo enumerar 2^n subconjuntos; e a extração de campos de vários bits e DP com máscara de bits usam the mesmos princípios de mascaramento para codificar estados mais complexos. A seguir, exploraremos a contagem de bits, números ausentes e inversão de bits usando as técnicas desta e da lição anterior.
Perguntas Frequentes
A aula “Máscaras de bits: definir, limpar, alternar e verificar” é grátis?
Sim — o texto completo de “Máscaras de bits: definir, limpar, alternar e verificar” é 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 “Máscaras de bits: definir, limpar, alternar e verificar”?
Implemente funções auxiliares para definir, limpar, alternar e verificar bits individuais e aplique máscaras de bits para representar subconjuntos em problemas de enumeração de subconjuntos. 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 3 de 4.
Quanto tempo leva a aula “Máscaras de bits: definir, limpar, alternar e verificar”?
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
- Operadores bit a bit: AND, OR, XOR, NOT e deslocamentos
- Número único e propriedades de XOR
- Máscaras de bits: definir, limpar, alternar e verificar
- Contagem de bits, número ausente e inversão de bits