CodeIQ MAGAZINECodeIQ MAGAZINE

世界一簡単な?ビット演算の覚え方 #アルゴリズム

2014.03.10 Category:技術コラム Tag:

  • 25
  • このエントリーをはてなブックマークに追加
001アイキャッチ

ビット演算というと、どことなく苦手意識を持っている人もいるのではないでしょうか?

ここでは数学や回路図、ド・モルガンの法則のような難しそうな話はせずに、ビット演算子の特徴とどういった用途にどの演算子を使ったらいいかにフォーカスして説明します。
by 株式会社クラフトマンソフトウェア 野澤 秀仁

NOT ~

NOTは一番単純な演算です。 全てのビットを反転させる と覚えるだけです。

~ 1010 = 0101

XOR ^

XOR(エクスオア)は排他的論理和という名前からは難しそうなイメージがありますが、考え方は簡単です。 一部のビットを反転させる と覚えるだけです。NOTの部分バージョンと考えるといいでしょう。

1010 ^ 0011 = 1001

反転させたいビットは 1 に、そのままにしておきたいビットは 0 にします。

OR |

OR演算子はとても寛大です。1だろうが0だろうが、どんな入力でも「いいよ、いいよ」とビットを立ててしまいます。つまり、 ビットをONにする能力 があります。

1010 | 0011 = 1011

ONにしたいビットは 1 に、そのままにしておきたいビットは 0 にします。

AND &

OR演算子と比べると、AND演算子は厳しい関税職員のようです。ANDはOFFしたいビットのブラックリストを持っていて、「ダメなものはダメ」とビットを0にします。つまり、 ビットをOFFにする能力 があります。

1010 & 1100 = 1000

OFFにしたいビットは 0 に、そのままにしておきたいビットは 1 にします。

ここだけ覚えればOK! 逆引きビット演算

以上をまとめるとこのようになります。

やりたいこと 演算方法 演算子 変更したいビット そのままにしたいビット
ビットをすべて反転させたい NOT ~ すべて変更される 指定不可
一部のビットを反転させたい XOR ^ 反転させたいビット: 1 0
一部のビットをONにしたい OR ONにしたいビット: 1 0
一部のビットをOFFにしたい AND & OFFにしたいビット: 0 1

ビット演算どこで役立つ?

最も効率的な活用場面として、複数のYes/Noの状態をひとつのオブジェクトやエンティティに持たせるケースです。Unixファイルシステムのアクセス制御などはその例です。読み込み可能か、書き込み可能か、実行可能かのそれぞれのパーミッションをビットで管理しています。

それぞれ3つの状態を個別にもたせると3バイト(SQLで言えば3カラム)必要になりますが、ビットにすれば1バイト(SQLで言えば1カラム)ですみます。ファイルシステムやデータベースのように大量のデータにそれぞれフラグを持たせる場合に、ビットで管理するとデータ量を節約できるわけです。

このようなフラグ管理が行われている例として

  • Unix/Linuxファイルシステムのパーミッション
  • PHPのerror_reporting(出力するエラーの種類の設定)などのプログラミング言語の設定値
  • TCP/IPのサブネットマスク
  • ゲームや業務システムの状態管理

などがあります。

また、フラグ管理以外にもアルファベットに対して10進数32でXOR演算を行うと大文字/小文字を変換できます。さらにJavaScriptなど一部の言語では、小数に対してNOT演算を2回行うと、整数部分を取り出せたりといった処理に応用することができます。

Goで大文字小文字を変換する例:

package main

func main() {
    println(string('a' ^ 32)) // A
    println(string('A' ^ 32)) // a
}

JavaScriptで小数点以下を切り捨てる例:

console.log(~~ 12.345) // 12

まとめ

演算子の特徴と「どういった用途にどの演算子を使ったらいいか」という観点から、演算子について解説しました。なかなか馴染みにくいというイメージのあるビット演算ですが、この記事を切っ掛けに少しでも身近に感じてもらえるといいのかなと思います。

ビット演算がわかるようになると、ビットマスク(AND)や、効率的なフラグの管理、大文字/小文字の変換(XOR)などに応用することができます。ビットマスクの便利な使いどころを調べてみてはいかがでしょうか。

CodeIQコード銀行にあなたのコードを預けてみませんか?

  • CodeIQコード銀行ではあなたのコードを財産と考えます。
  • お預かりいただいたコードは、CodeIQコード銀行がしっかり評価し、フィードバックいたします。
  • 当コード銀行にお預けいただいたコードは、企業がみてスカウトをかける可能性があります。
  • 転職したい方や将来転職することを考えている方で、今の自分のスキルレベルを知りたい方はぜひ挑戦してみてください。
  • 企業からスカウトがきたら困る人は挑戦しないでください。

興味を持った方はこちらからチャレンジを!

  • 25
  • このエントリーをはてなブックマークに追加

■この記事を書いた人

avatar

株式会社クラフトマンソフトウェア 野澤 秀仁

自動UIテストを支援するTaaS「ShouldBee」の開発者。「エンジニアリングは創造的で楽しくあるべき」のために、テスト・運用など退屈な作業の自動化やドメイン駆動設計を実施する。 twitter: @suin ブログ: http://blog.craftsman-software.com/

■関連記事

音声認識・画像認識に用いられる弾性マッチングのアルゴリズムって一体?... 音声認識・画像認識の進化が止まらない このような音声認識に関する研究は多くあり、またそれにより精度は飛躍的に良くなっています。 また写真を撮る際に人の顔を認識しフォーカスを当てる技術や、多くの写真のデータからAさんの写っている写真はこれ、Bさんの写っている写真はこれとこれ、と自動で選ぶ技術など、...
『数学ガール』とプログラミングの関係... はじめに こんにちは、結城浩です。 一年ぶりにCodeIQでアルゴリズムの問題を出題することになりました。 現在「マヨイドーロ問題」として出題中です。 ぜひみなさんチャレンジしてくださいね。 結城浩の「マヨイドーロ問題」 さて、今日は「『数学ガール』とプログラミングの関係」という題で、 少...
画像検索の精度を上げたスマホと、機械学習が起こしたWebの進化─森正弥×アラ若菜のWeb講座4... SIFTやSURFの登場でコモディティ化した画像検索技術 森:前回は自然言語処理の話をしましたが、今回は「画像UI」について話していきたいと思います。画像検索はここ数年で高度なものに進化しています。すでにコモディティ化されているので、楽に検索できるようになりましたが、アラさんは画像検索って使い...
日本の新聞は全部書いていることが同じなのか?トピック分析で見る新聞社説... トピック分析で検証する新聞社説 日本の新聞発行部数の第一位は読売新聞、第二位は朝日新聞です。実はこの二紙は世界の中でも発行部数上位二紙です。毎日新聞、中日新聞、日経新聞なども上位に入っています。 産経新聞は少し下ですが、それでもトップ20には入ります。人口比の発行部数でも日本はずっと上位です。最...
【日常に潜む最適化問題】受験者をなるべく均等に試験会場に割り振るアルゴリズム... 日常の動的計画法:受験者をなるべく均等に分割する 問題です。多数の受験者の集う試験の会場運営を任されました。 試験会場は全部で10あり、受験者を会場に割り振らなくてはいけません。 目的は、各部屋の受験者数の分散を最小にすることです。 ただし、次のようなルールがあります。 ルール1:名前の頭文字が...
「結城浩さんのCodeIQ問題は、なぜ面白いのか?」を7つのポイントで解説!... はじめに こんにちは、結城浩です。いつもCodeIQでの出題にご解答いただき、ありがとうございます。 今日は、CodeIQで出題しているときに私が心がけていることをお話しします。 なお、以下でお話しすることはあくまで私が出題する問題に対する心がけです。CodeIQにはたくさんの出題者さんがバリ...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ