C LANGUAGE TECHNOLOGY

【C言語】ビット演算とシフト演算の応用:回転,セット/クリア,スキャン,カウント【x86/ARM命令のコード】

悩んでいる人

C言語でビット演算とシフト演算の応用を教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

C言語でビット演算とシフト演算の応用

C言語でビット演算とシフト演算の応用を紹介します.

ビット演算とシフト演算の応用は,OSの実装でよく利用されるので使いこなせるようにしましょう.

ビット演算とシフト演算を基本から学びたいあなたは,こちらを読むことをおすすめします.

C言語 ビット演算子 シフト演算子
【C言語】ビット演算子とシフト演算子の使い方

こういった悩みにお答えします. こういった私から学べます. 目次1 ビット演算子2 &:ビット毎のAND(論理積)3 |:ビット毎のOR(論理和)4 ^:ビット毎のXOR(排他的論理和)5 ~ ...

続きを見る

ビットとシフト演算をバイト単位で行う例として,バイトスワップがあります.

バイトスワップを学びたいあなたはこちらからどうぞ.

C言語 バイトスワップ
【C言語】バイトオーダーの交換(バイトスワップ)方法の紹介【x86命令のコード】

こういった悩みにお答えします. こういった私から学べます. 目次1 C言語でバイトオーダーの交換(バイトスワップ)2 整数のバイトスワップ2.1 bswap_16/bswap_32/bswap_64関 ...

続きを見る

ビットの回転

ビットの回転とは,レジスタの最上位ビットと最下位ビットがつながっているとみなして回転することです.

レジスタを1ビットだけ左回転すると最上位ビットが最下位ビットに設定され,他のビットは1ビット左にシフトします.

レジスタを1ビットだけ右回転すると最下位ビットが最上位ビットに設定され,他のビットは1ビット右にシフトします.

ビットの回転を行う関数のコードは以下になります.

  • bit_left_rotation8関数:8ビットのレジスタu8をrビットだけ左回転
  • bit_right_rotation8関数:8ビットのレジスタu8をrビットだけ右回転
  • bit_left_rotation16関数:16ビットのレジスタu16をrビットだけ左回転
  • bit_right_rotation16関数:16ビットのレジスタu16をrビットだけ右回転
  • bit_left_rotation32関数:32ビットのレジスタu32をrビットだけ左回転
  • bit_right_rotation32関数:32ビットのレジスタu32をrビットだけ右回転
  • bit_left_rotation64関数:64ビットのレジスタu64をrビットだけ左回転
  • bit_right_rotation64関数:64ビットのレジスタu64をrビットだけ右回転

実行結果は以下になります.

ビットのセット/クリア

レジスタの特定ビットをセット(1に設定)やクリア(0に設定)する処理は,CPUの制御レジスタを操作するためによく利用します.

他にも,特定ビットがセットされているかどうか判定したり,特定ビットを反転させる操作(0の場合は1,1の場合0に設定)もよく利用します.

ビットのセット/クリアするコードは以下になります.

実行結果は以下になります.

ビットのスキャン

ビットのスキャンとは,レジスタの中で最も最初にビットがセットされている(1になっている)場所を検索することを言います.

ビットを最下位ビットから最上位ビットにスキャンするのはfind_first_bit関数,最上位ビットから最下位ビットにスキャンするのはfind_last_bit関数となります.

例えば,32ビットのレジスタでは以下のような結果になります.

  • 32ビットのレジスタの最下位ビットのみが1の場合(0x00000001),find_first_bit/find_last_bit関数の戻り値は両方とも0
  • 32ビットのレジスタの最上位ビットのみが1の場合(0x80000000),find_first_bit/find_last_bit関数の戻り値は両方とも31
  • 32ビットのレジスタの最上位ビットと最下位ビットが0の場合(0x80000001),find_first_bit関数の戻り値は0,find_last_bit関数の戻り値は31
  • 32ビットのレジスタが0の場合,find_first_bit/find_last_bit関数の戻り値は0

ビットをスキャンする関数

ビットをスキャンする関数のコードは以下になります.

実行結果は以下になります.

x86のbsf/bsr命令

x86(x64を含む)のbsf/bsr命令を利用するコードは以下になります.

  • bsf命令:Bit Scan Forwardの略で,レジスタで1にセットされている最も高いビットの位置を返します.
  • bsr命令:Bit Scan Reverseの略で,レジスタで1にセットされている最も低いビットの位置を返します.

※bsf/bsr命令は16/32/64ビット用なので8ビット用のコードはありません.

実行結果は以下になります.

ビットのカウント

ビットのカウントする方法を紹介していきます.

ビットのカウントでは,主に以下の処理があります.

  • レジスタの1の個数をカウント
  • レジスタの最上位ビット/最下位ビットから0が連続する個数のカウント

ビットをカウントする関数

ビットをカウントする関数のコードは以下になります.

実行結果は以下になります.

x86のpopcnt/tzcnt/lzcnt命令

x86のpopcnt/tzcnt/lzcnt命令を利用するコードは以下になります.

  • popcnt命令:レジスタの1に設定されているビットの個数をカウント
  • tzcnt命令:レジスタの最上位ビットから0が連続する個数をカウント
  • lzcnt命令:レジスタの最上位ビットから0が連続する個数をカウント

popcnt/tzcnt/lzcnt命令は16/32/64ビット用なので8ビットのコードはありません.

実行結果は以下になります.

ARMのclz命令

ARMのclz命令を利用するコードは以下になります.

※clz命令は32/64ビット用かつ64ビット用のコンパイラでビルドするので,8/16/32ビット用のコードはありません.

Intel CPU上でARMのクロス開発環境の構築方法は,以下の記事を参考にして下さい.

C言語 ラズパイ3
【C言語】Raspberry Pi 3のユーザモードとカーネルモードでプログラムの実行

こういった悩みにお答えします. こういった私から学べます. 目次1 Raspberry Pi 32 Raspberry Pi 3のエミュレータ「QEMU」3 Raspberry Pi 3でC言語のプロ ...

続きを見る

実行結果は以下になります.

まとめ

C言語でビット演算とシフト演算の応用として回転,セット/クリア,スキャン,カウントと,x86/ARM命令のコードを紹介しました.

これらの処理はOSの実装でよく利用されるので,使い方をきちんと理解しましょう!

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , , , , , , , , , , ,