n & (n-1), что делает это выражение?

Он выясняет, является ли n равным 0 или точной мощностью двух.

Это работает, потому что двоичная сила двух имеет вид 1000...000 и вычитание одного даст вам 111...111 . Затем, когда вы вместе с ними, вы получаете нуль, например:

  1000 0000 0000 0000 & 111 1111 1111 1111 ==== ==== ==== ==== = 0000 0000 0000 0000 

Любое входное значение без мощности (отличное от нуля) не даст вам нуля при выполнении этой операции.

Например, давайте попробуем все 4-битные комбинации:

  <----- binary ----> nn n-1 n&(n-1) -- ---- ---- ------- 0 0000 0111 0000 * 1 0001 0000 0000 * 2 0010 0001 0000 * 3 0011 0010 0010 4 0100 0011 0000 * 5 0101 0100 0100 6 0110 0101 0100 7 0111 0110 0110 8 1000 0111 0000 * 9 1001 1000 1000 10 1010 1001 1000 11 1011 1010 1010 12 1100 1011 1000 13 1101 1100 1100 14 1110 1101 1100 15 1111 1110 1110 

Вы можете видеть, что только 0 и полномочия двух ( 1 , 2 , 4 и 8 ) приводят к шаблону бита 0000/false , все остальные отличны от нуля или true .

Он возвращает 0, если n – мощность 2 (NB: работает только при n > 0 ). Таким образом, вы можете протестировать силу 2 следующим образом:

 bool isPowerOfTwo(int n) { return (n > 0) && ((n & (n - 1)) == 0); } 

Он проверяет, является ли n мощностью 2: что делает побитовый код «$ n & ($ n – 1)»?

Это побитовая операция между числом и его предыдущим номером. Только это выражение может быть ложным, если n – это сила 2, так что вы, по сути, проверяете, не является ли это силой 2.