【Python】Atcoderで使われるビット演算・ビットシフト・bit全探索についてまとめる

この記事は約6分で読めます。

bit演算、bit全探索について勉強しました。

いくつかのWebページや書籍に当たってみたので、自分なりに調べた内容をまとめておきます。

bit全探索とは

選ぶ/選ばない2択がn回あり、その全パターン(2のn乗回)を調べる時に用いる探索方法です。

以下のような問題を考えるときに使うことができます。

・YesかNoで答える問題が2のn乗個ある。

・n人が皿1か皿2のどちらかにボールを載せる

・n桁の数字abcd・・・について、各桁の間に+か-のどちらかを入れて計算結果をxにする

・n冊の本の選び方の全パターンを列挙する

n回の選択肢のそれぞれについて、選ぶ/選ばないという選択肢が2つあることから、選ばないことを0、選ぶことを1のbitとして考え、全てのパターンを繰り返しながら調べていきます。

全パターン調べるので、全探索の一種ですが、そこにbit操作が含まれています。

bit全探索について考える前に、2進数とbit操作について振り返ります。

基本のコード

まずは全パターンを列挙するためのコードを記載します。

このコードを使いまわしつつ、問題に合わせて中身の処理や判定を変更しています。

以下は選ぶを1、選ばないを0として、3つの本の選び方の組み合わせについて全パターンを列挙しています。

Atcoderで使うことができるようにまずは使いまわせるコードを紹介しましたが、

以降では2進数などbit全探索の前提となる知識について記載していきます。

Pythonでの2進数と10進数の扱い

2進数として扱う

私たちが普段使っている数字は10進数と呼ばれますが、bit全探索ではbit演算を行うために2進数を扱います。

10進数での”10″は2進数では”1010″になります。

“1010”をそのままnに代入すると扱いなれている10進数として代入されます

そこで、”0b”を先頭につけることで”1010″を2進数として代入することができます。

※”bin()”については次の項目に記載しました。

2進数で表示

10進数の”10″を2進数で表示してみます。

“n=10″で10進数の”10″をnに代入しました。

つづいて”print(bin(n))”とすることで2進数の”1010″として表示することができます。

ビット操作について

bit演算

ビット演算とは2進数の演算をすることです。

整数(2進数)の各桁のビットについて、論理演算を一度に行います。

以下の2つの2進数についてビット演算を行ってみます。

“11011100” 10進数では”220″

“10110110” 10進数では”182″

AND(論理積)

“11011100”と”10110110″の各桁で演算を行います。

各桁について、どちらも1ならば1、いずれかが0なら0になります。

Pythonでの演算子は”&”です。

11011100

10110110

10010100

 

OR(論理和)

“11011100”と”10110110″の各桁で演算を行います。

各桁について、いずれか一方でも1なら1になります。

11011100

10110110

11111110

 

XOR(排他的論理和)

“11011100”と”10110110″の各桁で演算を行います。

各桁について、一致なら0に、不一致なら1になります。

11011100

10110110

01101010

2進数で表示した時、先頭の桁が0であった場合は”0b01101010″とはならず、”0b1101010″と表示されています。表記は省略されているだけで、0で埋められています。

NOT(否定)

“11011100”と”10110110″のそれぞれで演算を行います。

1と0が反転します。

11011100

00100011

 

10110110

01001001

 

bitシフト

左シフト

1bit左シフトすると2倍、2bit左シフトすると4倍になります。

2進数の”10010″が、2進数の”100100″になりました。

左シフトすると、各桁の数字が1桁ずつ左にすれます。そして右端に0が入ります。今回は1bit左シフトしたので右端に0が1つ加わりました。

右シフト

1bit右シフトすると2分の1、2bit右シフトすると4分の1になります。

2進数の”110110″が”11011″になりました。

右シフトした場合は、各桁の数字が1桁ずつ右にずれます。右端の桁の数字はシフトした分だけそのまま切り捨てられます。

今回は1bit右シフトしたので、右端の0が切り捨てられました。

問題

ABC 079 C Train Ticket

ARC 061 C たくさんの数式

参考

この記事を作成するにあたりこれらの情報を参考にさせて頂きました。

Webサイト

bit演算

Python ビット演算 超入門 – Qiita

Python3での2の補数と~演算子(ビット反転) (zenn.dev)

Pythonのビット演算の使い方: 左シフト、右シフト、論理積、論理和、排他的論理和、反転など – なるぽのブログ (yu-nix.com)

bit全探索

bit 全探索 – けんちょんの競プロ精進記録 (hatenablog.com)

この記事が一番わかりやすかったです。

Python de アルゴリズム(bit全探索) – Qiita

bit全探索について触れてから、早速例題を通して実装方法を紹介しています。

AtCoder 版!蟻本 (初級編) – Qiita ※項目2.1に記載

Atcoder上でのbit全探索の類題が5問紹介されています。

ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜 – Qiita

bit演算を含んだ応用問題まで解説があります。

書籍

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~

競技プログラミングで使うbitシフトは、こちらでは算術シフトと記載されています。このほかに論理シフトについて記載されています。また、bit演算だけでなく、一般的なbit操作についてコード付きで紹介されています。C++で記載されています。

Pythonではじめるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量

コラムでbit演算について触れられています。図と表を使って説明しているので直感的につかみやすいです。文量はコンパクトに収まっていますが、かえって読みやすいです。

 

コメント