0Pricing
Competitive Programming Academy · レッスン

ビット数と最下位の Set Bit

popcount と n & -n のテクニックを使います

「ビット数と最下位の Set Bit」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

1のビットを数える

多くの問題では、数値の中でセットされているビットの数を尋ねます。これはpopcountと呼ばれ、部分集合の大きさやパリティの確認、スコア計算などに登場します。🔢

Python組み込みのカウント

セットビットを数える最も速い方法は、整数のメソッドbit_count()を使うことです。ループも手間もなく、1の数だけを取得できます。

print((13).bit_count())  # 0b1101 has 3 ones

binとcountで数える

bit_countを忘れた場合は、数値を2進数の文字列に変換して1の数を数えます。遅くはなりますが、分かりやすく覚えやすい方法です。

print(bin(13).count('1'))  # 3

最下位のセットビット

最下位のセットビットとは、数値の右端にある1のことです。これを分離する操作は、後でFenwick木や部分集合のテクニックに使う重要な手法です。

nと-nで分離する

有名なテクニックn & -nを使うと、最下位のセットビットだけを残せます。2の補数表現における負数の性質によって、このように動作します。

n = 12  # 0b1100
print(n & -n)  # 4 = 0b100

nと-nが機能する理由

符号を反転するとすべてのビットが反転して1が加わるため、最下位の1より下にあるビットがすべて反転します。ANDを取ると、その1つのビットだけが残ります。

最下位のセットビットを取り除く

1を引くと末尾の0をさかのぼって繰り下がるため、n & (n - 1)は最下位のセットビットを消します。これを繰り返せば、1を1つずつ取り除けます。

n = 12  # 0b1100
print(n & (n - 1))  # 8 = 0b1000

Brian Kernighanのカウント

数値が0以外の間ループし、毎回最下位のビットをクリアします。セットビット1つにつき1回だけループするため、セットビットが少ない場合のpopcountに適しています。

c = 0
while n:
    n &= n - 1
    c += 1

2のべき乗か確認する

正の2のべき乗はセットビットをちょうど1つだけ持つため、n & (n - 1)は0になります。ANDを1回行うだけで、すぐに判定できます。

def is_pow2(n):
    return n > 0 and (n & (n - 1)) == 0

ビット数からパリティを求める

数値のパリティは、popcountを2で割った余りにすぎません。1の数が奇数か偶数かを、1回の処理で判定できます。

parity = (13).bit_count() & 1  # 1

最速の方法を選ぶ

速度を最優先するならbit_countを使い、セットビットを順にたどるならn & (n-1)のループを使います。適切な方法を選ぶと、厳しい制限時間にも対応できます。⚡

確認問題

最下位のセットビットを取り出すテクニックを試してみましょう。

復習: ビットのカウント

bit_countで1の数を数え、n & -nで最下位のビットを分離し、n & (n-1)でそれを取り除けます。強力な1行処理です。🎉

よくある質問

「ビット数と最下位の Set Bit」レッスンは無料ですか？

はい。「ビット数と最下位の Set Bit」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「ビット数と最下位の Set Bit」で何を学びますか？

popcount と n & -n のテクニックを使います ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「ビット数と最下位の Set Bit」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. AND、OR、XOR、シフト
  2. ビットの Set、Clear、Toggle
  3. ビット数と最下位の Set Bit
  4. 小さな集合としてのビットマスク
← Competitive Programming Academyに戻る