スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ビット演算基本技集

C 言語におけるビット演算の基本テクニックを自分のためにメモ。

基本技集

以下では、最下位を 0 ビット目と数えます。また、n は unsigned int 型とします。プログラム中、unsigned と型指定したものは、unsigned int 型として処理されます。定数の後ろにある U は、その定数が unsigned int 型であることを表します。

/* Nビット目を取り出す */
(n >> N) & 1

/* Nビット目に1をセットする */
n = n | (1 << N);

/* Nビット目に0をセットする */
n = n & ~(1 << N);

/* Nビット目を反転 */
n = n ^ (1 << N);

/* 0ビット目からN-1ビット目までがすべて1である列の生成 */
n = (1 << N) - 1;

/* 全ビットの反転 (1) */
n = ~n

/* 全ビットの反転 (2) */
n = n ^ ~0

/* unsigned int の最上位ビットの値 (1) */
1 << ( sizeof(unsigned) * 8 - 1 )

/* unsigned int の最上位ビットの値 (2) */
~(~0U >> 1)

/* 1である最も下位のビットの値を抽出 */
-n & n

/* 2のi乗倍する */
n <<= i;

/* 2のi乗で割る */
n >>= i;

/* 2のi乗で割った剰余 */
n & ((1 << i) - 1)

/* 奇数かどうかの判定 */
if ( n & 1 ) { /* 奇数 */ }

ビット列の表示

void display_bits( unsigned n )
{
  unsigned mask = 1 << ( sizeof(unsigned) * 8 - 1 );

  do {
    printf( "%d", (n & mask) ? 1 : 0 );
  } while ( mask >>= 1 );
  printf("\n");
}

値の交換

void swap( unsigned *a, unsigned *b )
{
  *a = *a ^ *b;
  *b = *b ^ *a;
  *a = *a ^ *b;
}

ビットを逆順に並べ替える (32bit)

unsigned reverse_bits( unsigned n )
{
  n = (n & 0x55555555) <<  1 | (n >>  1 & 0x55555555);
  n = (n & 0x33333333) <<  2 | (n >>  2 & 0x33333333);
  n = (n & 0x0f0f0f0f) <<  4 | (n >>  4 & 0x0f0f0f0f);
  n = (n & 0x00ff00ff) <<  8 | (n >>  8 & 0x00ff00ff);
  n = (n & 0x0000ffff) << 16 | (n >> 16 & 0x0000ffff);

  return n;
}

1 であるビットの個数をカウント (32bit)

unsigned count_1_bits( unsigned n )
{
  n = (n & 0x55555555) + (n >>  1 & 0x55555555);
  n = (n & 0x33333333) + (n >>  2 & 0x33333333);
  n = (n & 0x0f0f0f0f) + (n >>  4 & 0x0f0f0f0f);
  n = (n & 0x00ff00ff) + (n >>  8 & 0x00ff00ff);
  n = (n & 0x0000ffff) + (n >> 16 & 0x0000ffff);

  return n;
}

1 である最も上位のビットを抽出 (32bit)

unsigned leading_1_bit( unsigned n )
{
  n = n | (n >>  1);
  n = n | (n >>  2);
  n = n | (n >>  4);
  n = n | (n >>  8);
  n = n | (n >> 16);

  return n ^ (n >> 1);
}

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。