Nas competições de programação, uma pequena margem de tempo pode ser suficiente para decidir o vencedor e o perdedor. Por isso, velocidade para encontrar a resposta é um critério de desempate muito comum. Sabendo disso, muitas equipes implementam versões super otimizadas dos algoritmos para obterem melhores resultados. Algoritmos bitwise são muito comuns nessas soluções, pois operações com bits podem ser executados de forma extremamente rápidas e existem diversos algoritmos que se aproveitam de propriedades da manipulação de bits.

Limpar o bit 1 mais a direita

A expressão N & (N-1) resulta em um valor muito interessante: ela retorna o valor de N transformando o bit 1 mais a direita em 0. Vamos supor o seguinte caso:

2610 = 110102
2510 = 110012
110102 & 110012 = 110002

O número 11000 corresponde ao 11010 com o bit 1 mais a direito flipado para 0.

Checar se somente 1 bit está setado

Com a expressão para setar o bit 1 mais a direita em 0, conseguimos implementar um algoritmo muito útil: detectar se há somente um bit 1. Vamos analisar: se há somente um bit 1 no número, quando este for transformado em 0, não haveria nenhum outro bit 1 no número. Portanto, o número seria igual a zero. Logo, se N & (N-1) for igual a zero e N não for zero, significa que só há um bit 1 no número N.

Se N for 11010, 
N & (N-1) = 11010 & 11001 = 110002
Como N & (N-1) != 0, N tem mais de um bit 1

Se N for 10000,
N & (N-1) = 10000 & 01111 = 00000
Como N !=0 e N & (N-1) = 0, N tem apenas 1 bit 1.

Se N for 0, N não tem nenhum bit 1 .

Brian Kernighan’s algorithm

Usando novamente a expressão N & (N – 1), podemos implementar um algoritmo muito engenhoso para calcular a quantidade de bits 1: Brian Kernighan’s algorithm. Enquanto, o número não for 0, haverá bits 1. Usando a expressão para remover apenas o bit 1 da direita, conseguimos contar quantas vezes precisamos fazer isso até o número virar 0.

def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)  # Clears the rightmost set bit
        count += 1
    return count

Uma observação é que esse algoritmo só funciona se n >= 0.