A manipulação de bits é uma técnica simples e poderosa que pode ser útil na resolução de questões propostas em entrevistas de programação. Ainda que seja baseada em operações triviais, dominar essa técnica e colocá-la na sua caixa de ferramentas imaginária de técnicas para resolução de problemas é bastante vantajoso, especialmente quando o contexto do desafio em questão naturalmente se encaixa com uma abordagem que utiliza operações com bits.
Aqui serão apresentadas as principais operações com bits comumente encontradas nas linguagens de programação e exemplos de resoluções de questões onde a solução desenvolvida utiliza esta técnica.
Operações com bits
As principais operações com bits podem ser classificadas como operações bit-a-bit e operações de deslocamento de bits. Operações bit-a-bit compreendem quatro tipos: NOT, AND, OR e XOR. Já as operações de deslocamento de bits compreendem o deslocamento à esquerda e o deslocamento à direita.
Operador NOT
O operador NOT funciona invertendo o bit em questão. A maioria das linguagens de programação utiliza o caractere ~ para essa operação. O resultado da operação NOT se dá replicando a operação em cada um dos bits do valor original, sendo esse resultado chamado de complemento.
+-------+------------+
| bit a | NOT a (~a) |
+-------+------------+ ~100101110
| 0 | 1 | ---------
| 1 | 0 | = 011010001
+-------+------------+
Operador AND
O operador AND possui dois operandos e tem como resultado um bit ativo apenas quando ambos operandos são bits ativos. A maioria das linguagens de programação utiliza o caractere & para essa operação. O resultado da operação AND se dá replicando a operação em cada um dos pares de bits dos operandos, respeitando a posição dos bits.
+-------+-------+-----------------+
| bit a | bit b | a AND b (a & b) |
+-------+-------+-----------------+
| 0 | 0 | 0 | 100110011
| 0 | 1 | 0 | & 101110000
| 1 | 0 | 0 | ---------
| 1 | 1 | 1 | = 100110000
+-------+-------+-----------------+
Operador OR
O operador OR possui dois operandos e tem como resultado um bit ativo quando pelo menos um dos operandos é um bit ativo. A maioria das linguagens de programação utiliza o caractere | para essa operação. O resultado da operação OR se dá replicando a operação em cada um dos pares de bits dos operandos, respeitando a posição dos bits.
+-------+-------+----------------+
| bit a | bit b | a OR b (a | b) |
+-------+-------+----------------+
| 0 | 0 | 0 | 110100001
| 0 | 1 | 1 | | 101010001
| 1 | 0 | 1 | ---------
| 1 | 1 | 1 | = 111110001
+-------+-------+----------------+
Operador XOR
O operador XOR (Exclusive OR) possui dois operandos e tem como resultado um bit ativo quando apenas um dos operandos é um bit ativo. A maioria das linguagens de programação utiliza o caractere ^ para essa operação. O resultado da operação XOR se dá replicando a operação em cada um dos pares de bits dos operandos, respeitando a posição dos bits.
+-------+-------+-----------------+
| bit a | bit b | a XOR b (a ^ b) |
+-------+-------+-----------------+
| 0 | 0 | 0 | 110100001
| 0 | 1 | 1 | ^ 101010001
| 1 | 0 | 1 | ---------
| 1 | 1 | 0 | = 011110000
+-------+-------+-----------------+
Algumas propriedades importantes da operação XOR:
a XOR a = 0
a XOR 0 = a
se (a ≠ b) então (a XOR b ≠ 0)
Deslocamentos
As operações de deslocamento de bits para a esquerda e para a direita são bastante similares. Ambas operações possuem dois operandos, o valor original a se aplicar o deslocamento e um inteiro n representando o número de unidades a serem deslocadas. Propriedades do deslocamento de bits relacionadas com multiplicação e divisão são bastante interessantes para a resolução de certas questões.
Deslocamento à Esquerda
Realizar um deslocamento à esquerda de n unidades sobre uma representação binária consiste em deslocar cada um de seus bits n posições para a esquerda, respeitando a ordem dos bits e preenchendo os espaços vazios com bits 0. Essa operação pode ser entendida então como uma adição de n bits de valor 0 nas posições menos significativas do valor original.
Um detalhe sobre essa operação é que bits mais significativos do valor original podem "desaparecer", caso o deslocamento seja grande o suficiente. Da mesma forma, se o número de unidades deslocadas for superior ao número de bits da representação original, o resultado pode ser zerado.
A maioria das linguagens de programação usa o símbolo << seguido de um inteiro n para indicar um deslocamento à esquerda de n unidades.
00000001 << 3 = 00001000
00100101 << 2 = 10010100
01001010 << 4 = 10100000
01001010 << 8 = 00000000
Uma propriedade importante do deslocamento à esquerda é que cada unidade deslocada representa uma multiplicação por 2 sobre o valor original. Portanto, realizar uma operação a << n têm o mesmo efeito de multiplicar a por 2^n.
Para melhor visualizar essa propriedade, pode-se lembrar que multiplicar um número inteiro por 10^n no sistema decimal é o mesmo que lhe adicionar n dígitos de valor 0 nas posições menos significativas. De fato, trata-se da mesma ideia fundamental por trás dessa operação em ambos os sistemas (binário e decimal).
0000 0111 << 1 = 0000 1110
(7) * 2 = (14)
0000 1110 << 3 = 0111 0000
(14) * 8 = (112)
Deslocamento à Direita
De forma análoga, realizar um deslocamento à direita de n unidades sobre uma representação binária consiste em deslocar cada um de seus bits n posições à direita, respeitando a ordem dos bits e preenchendo os espaços vazios com bits 0. Essa operação pode ser entendida então como a remoção dos n bits menos significativos do valor original juntamente com a adição de n bits 0 nas suas posições mais significativas.
A maioria das linguagens de programação usa o símbolo >> seguido de um inteiro n para indicar um deslocamento à direita de n unidades.
00001000 >> 2 = 00000010
10110101 >> 3 = 00010110
01001111 >> 4 = 00000100
01001010 >> 8 = 00000000
Uma propriedade importante do deslocamento à direita é que cada unidade deslocada representa uma divisão inteira por 2 sobre o valor original. Portanto, realizar uma operação a >> n têm o mesmo efeito de dividir a por 2^n.
Para melhor visualizar essa propriedade, pode-se lembrar que a parte inteira da divisão de um número inteiro por 10^n no sistema decimal é o mesmo que lhe remover n dígitos de suas posições menos significativas. De fato, trata-se da mesma ideia fundamental por trás dessa operação em ambos os sistemas (binário e decimal).
1110 1101 >> 1 = 0111 0110
(237) / 2 = (118)
0111 0110 >> 4 = 0000 0111
(118) / 16 = (7)
Questões com Manipulação de Bits
LeetCode 78 - Subsets
O problema pede para, dado um array de inteiros A, retornar arrays com todos os subconjuntos de A. Essa questão traz um uso clássico de manipulação de bits, que é a representação de subconjuntos.
Um inteiro pode representar um subconjunto de maneira única da seguinte forma: o i-ésimo bit indica se o i-ésimo elemento está ou não no subconjunto. Por exemplo, usando 1 para inclusão e 0 para exclusão, tendo o array A = [5,2,3,8,7], o inteiro de 5 bits cuja representação binária consiste em 01001 representa o subconjunto [2,7].
Com isso, sendo n o tamanho do array, cada inteiro de 0 até 2^(n)-1 é uma máscara de bits que representa um dos subconjuntos. Basta iterar em cada uma dessas máscaras seu respectivo o subconjunto. Para construir o subconjunto dada uma máscara, precisamos saber quais bits estão ativos ou não nessa máscara. Para fazer isso, podemos usar os operadores de deslocamento e AND, conforme será apresentado a seguir.
Se queremos saber se o i-ésimo bit de um inteiro V está ativo, podemos primeiro deslocar esse bit para a posição menos significativa através do deslocamento para a direita (V >> i). Após fazer isso, o i-ésimo bit vai ficar na posição 0, e para saber se ele está ativo, basta fazer um AND com o inteiro 1. Com isso, todos os outros bits ficarão inativos (pois estão inativos na representação do 1), então o resultado de (V >> i) & 1 será 1 se o i-ésimo bit estiver ativo, e 0 se não estiver.
Segue abaixo o código da solução em Python para esse problema:
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
n = len(nums)
subsets = []
for mask in range(1 << n):
subset = [nums[i] for i in range(n) if (mask >> i) & 1]
subsets.append(subset)
return subsets
LeetCode 136 - Single Number
O problema pede para receber um array de elementos onde cada número aparece duas vezes, exceto um, e retornar o elemento que só aparece uma vez.
Como qualquer elemento operado com ele mesmo através do XOR resulta em 0, que é o elemento neutro da operação, se calcularmos o XOR entre todos os elementos do vetor, cada par de elementos será anulado, e o resultado final será justamente o número que só aparece uma vez. Note que a ordem dos elementos não importa, uma vez que a operação XOR, assim como OR e AND, é comutativa e associativa.
Segue o código com a solução em Python:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ret = 0
for x in nums:
ret ^= x
return ret
LeetCode 137 - Single Number II
O problema é similar ao anterior, porém, cada elemento aparece três vezes no vetor, exceto um. Pede-se para identificar esse elemento que aparece uma única vez.
A solução é similar ao problema anterior, porém deve-se generalizar a ideia do XOR. O XOR de cada bit diz basicamente se esse bit apareceu ativo uma quantidade par de vezes ou não. É equivalente a contar quantas vezes cada bit apareceu e depois tirar o resto da divisão por 2. Dessa forma, para esse problema a solução consiste em contar quantas vezes cada bit aparece, e depois verificar o resto na divisão por 3. Cada número que aparecer três vezes, fará com que o resto não mude, pois o contador de cada bit inativo será somado em 0, e o contador de cada bit ativo somará 3, não alterando o resto na divisão por 3. Como os inteiros possuem 32 bits, serão criados 32 contadores. No fim, o resto na divisão por 3 vai dar 1 exatamente nos bits do número que só aparece uma vez.
Segue abaixo o código em Python com a solução. Obs: como em Python não ocorre overflow, é preciso converter para inteiro com 32 bits o resultado, por causa dos números negativos.
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
import ctypes
contadores = [0] * 32
ret = 0
for x in nums:
for i in range(32):
if (x >> i) & 1:
contadores[i] += 1
for i in range(32):
if contadores[i] % 3 == 1:
ret += (1 << i)
return ctypes.c_int(ret).value
LeetCode 260 - Single Number III
Nesse problema, é dado um array onde cada elemento aparece exatamente duas vezes, exceto dois elementos, os quais aparecem exatamente uma vez cada um. O problema pede para retornar esses dois elementos.
Como vimos no Single Number (LeetCode 136), ao calcular o XOR de todos os elementos do vetor, os elementos que aparecem duas vezes se anulam. Então, sendo X e Y os dois números distintos que aparecem exatamente uma vez no array, o XOR de todos os elementos do array vai resultar em X XOR Y. Como X e Y são diferentes, esse resultado vai ser diferente de 0: cada bit ativo em X XOR Y indica que esse bit é diferente em X e em Y.
Note que com isso é possível saber todos os bits em que X e Y diferem. De fato, basta saber apenas um desses bits para calcular a resposta: suponha que o i-ésimo bit de X é diferente do i-ésimo bit de Y (isso é, o i-ésimo bit de X XOR Y está ativo), para algum i, e separe o array original em dois arrays, sendo um array contendo todos os elementos que têm o i-ésimo bit ativo, e outro contendo todos os elementos que contêm esse bit inativo.
Ao fazer essa separação, note que X e Y estarão em arrays diferentes, já que eles diferem no i-ésimo bit. Além disso, para os outros pares de elementos, os dois elementos de cada par estarão sempre no mesmo array, por serem iguais (uma vez que isso implica que eles possuem os mesmos bits ativos). Assim, teremos dois arrays onde cada um deles possui exatamente um elemento que aparece uma única vez, e os demais aparecem duas vezes. Basta então executar a solução do problema Single Number (LeetCode 136) em cada um desses arrays para encontrar ambos X e Y.
Para encontrar um bit ativo de X XOR Y, pode-se usar um truque que encontra o bit menos significativo de um número, devido a forma com que se modela complemento de 2, através da fórmula V & (-V), cujo resultado é sempre um número com apenas um bit ativo, correspondente ao bit menos significativo ativo em V, para qualquer V diferente de 0.
Abaixo segue a implementação dessa solução em Python:
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
xor = 0
for x in nums:
xor ^= x
bit = xor & (-xor)
left = [x for x in nums if x & bit == 0]
right = [x for x in nums if x & bit != 0]
return [self.singleNumberOne(left), self.singleNumberOne(right)]
def singleNumberOne(self, nums):
ret = 0
for x in nums:
ret ^= x
return ret
Conclusão
A manipulação de bits engloba operações e técnicas bem simples de se aprender e que podem ser essenciais na hora de se resolver uma questão durante uma entrevista de programação. Investir um tempo para dominar essas técnicas é algo que com certeza vai incrementar seu arsenal para resolver problemas em sua vida de desenvolvedor.
Autores: Carlos Vieira (@carlosemv), Leonandro Gurgel (@Leonandro), Thiago Lucena (@thiagocesarm) e Victor Agnez (@victoragnez).
Top comments (0)