n & (n - 1) == 0 の意味とは？

最近問題を解いていて

n & (n - 1) == 0

というような条件式をたまに見かけます。結論から言うとこれは n が0または2の累乗 (= )かどうかを判定する条件式なのですが、どうしてそうなるのか丁寧に見ていきたいと思います。

n - 1 を2進数で考えるとどうなる？

2進数表現の最下位ビットが1のケース

n = 0b???1というように、最下位ビットが1となっている場合を考えます。この場合 n - 1は単純で
n - 1 = 0b???0 となりますね。

最下位2ビットが10の場合

では、最下位ビットが0の場合はどうなるでしょうか。次に簡単なケースである、その左隣のビットが1の場合、つまり
n = 0b???10
という場合を考えてみます。この場合は
n - 1 = 0b???01
となりますね。

n = 0b???10...0の場合

少しわかりにくい書き方ですが、n = 0b???10...0という場合を考えます。これは、末尾に複数個の0が連続している("0...0"の部分)ケースです。この場合は
n - 1 = 0b???01...1
となります。

このように観察してみると、n - 1という計算はと「一番下位（右側）にある1のビットとそれより右側の0のビットをすべて反転させる」という操作になっていることがわかります。

n & (n - 1) はどうなる？

n = 0b???10...0 であるとします。表記上、末尾の0は2個以上必要なように見えますが、末尾の0の個数は0個でも1個でもOKです。
この場合、右端の1とその右側はすべて反転されていたので、ANDを取るとすべて0になります。

n = 0b???10...0
n - 1 = 0b???01...1

つまり、n & (n - 1) = 0b???00...0

n & (n - 1) == 0 の意味とは？

n & (n - 1) = 0b???00...0 が0になるのはどういうときかというと、???がすべて0の時です。つまり、この時nは

n = 0b0...010...0

のように、1であるビットが1つだけの値であったことになります。つまり、nが2の累乗であるときに、この条件式は真になります。
また当然ですが、n = 0の時もこの条件式は真となります。

よって、この式はnが0または2の累乗であるかどうかを判定する条件式だったのです。

参考問題

参考までに、最近この式を目にした箇所を紹介しておきます。

LeetCode 231 Power of Two

LeetCode の231問目に、次のような問題があります。

与えられた整数が2の累乗かどうかを判定する関数を書いてください。

https://leetcode.com/problems/power-of-two/

これはまさに今回の条件式が使えて、このコードで1発です。（コードはPythonの例）

class Solution(object):
    def isPowerOfTwo(self, n):
        return (n > 0) and (n & (n - 1) == 0)

世界で戦うプログラミング力を鍛える150問

世界で戦うプログラミング力を鍛える150問というコーディング面接の対策本があるのですが、この中の問題5.4に、n & (n - 1) == 0 の意味を説明する旨の問題が掲載されています。
今回の記事のような内容を説明することを求められている問題です。

世界で闘うプログラミング力を鍛える150問　トップIT企業のプログラマになるための本

LeetCode 338 Counting Bits

LeetCodeの338問目に、0～nまでの全てのiについて、iの2進数表現に含まれる1であるビットの数を計算する、という問題があります。
この問題も今回紹介したテクニックを使用して解くことができます。解説記事もあるので、興味のある方はそちらも参考にしてみてください。
www.madopro.net