Manipulação de bits para resolução de questões de entrevistas de programação
Tags: bitwise, bitshift, interview, codeinterview
Published: 2019-11-22 00:30:53

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](https://leetcode.com/problems/subsets/description/) 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:

```python
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](https://leetcode.com/problems/single-number/) 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:

```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](https://leetcode.com/problems/single-number-ii/) é 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.

```python
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](https://leetcode.com/problems/single-number-iii/), é 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:

```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](https://github.com/carlosemv)), Leonandro Gurgel ([@Leonandro](https://github.com/Leonandro)), Thiago Lucena ([@thiagocesarm](https://github.com/thiagocesarm)) e Victor Agnez ([@victoragnez](https://github.com/victoragnez)).