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

悩んでいる人

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

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

本記事の信頼性

リアルタイムシステムの研究歴12年．
東大教員の時に，英語でOS（Linuxカーネル）の授業．
2012年9月～2013年8月にアメリカのノースカロライナ大学チャペルヒル校（UNC）コンピュータサイエンス学部で客員研究員として勤務．C言語でリアルタイムLinuxの研究開発．
プログラミング歴15年以上，習得している言語: C/C++，Python，Solidity/Vyper，Java，Ruby，Go，Rust，D，HTML/CSS/JS/PHP，MATLAB，Verse（UEFN）, Assembler (x64，ARM)．
東大教員の時に，C++言語で開発した「LLVMコンパイラの拡張」，C言語で開発した独自のリアルタイムOS「Mcube Kernel」をGitHubにオープンソースとして公開．
2020年1月～現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務．2022年6月～現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO．
最近は自然言語処理AIとイーサリアムに関する有益な情報発信に従事．

（AI全般を含む）自然言語処理AIの論文の日本語訳や，AIチャットボット（ChatGPT，Auto-GPT，Gemini（旧Bard）など）の記事を50本以上執筆．アメリカのサンフランシスコ（広義のシリコンバレー）の会社でプロンプトエンジニア・マネージャー・Quality Assurance（QA）の業務委託の経験あり．
（スマートコントラクトのプログラミングを含む）イーサリアムや仮想通貨全般の記事を200本以上執筆．イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり．

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

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

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

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

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

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．こういった私が解説していきます．私が大学の授業で初めてC言語を勉強した時は全然できませんでしたが，先生やTA，友人に相談しながら一生懸命C言語を勉強してできるようにな ...

続きを見る

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

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

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

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

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

こういった悩みにお答えします．こういった私から学べます．ビット演算子ビット演算子とは，各々のビットに対する論理演算を一度に行う演算子のことです． C言語は本来はOSのようなシステム記述用の言語と ...

続きを見る

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

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

: 【C言語】バイトオーダーの交換（バイトスワップ）方法の紹介【x86-64命令のコード】

こういった悩みにお答えします．こういった私から学べます． C言語でバイトオーダーの交換（バイトスワップ） C言語でバイトオーダーの交換（バイトスワップ）方法を紹介します．バイトスワップはOSで利用 ...

続きを見る

ビットの回転

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

レジスタを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ビットだけ右回転

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdio.h>
#include <stdint.h>

uint8_t bit_left_rotation8(uint8_t u8, size_t r)
{
  r &= 0x7;
  return (uint8_t)(u8 >> (8 - r)) | (uint8_t)(u8 << r);
}

uint8_t bit_right_rotation8(uint8_t u8, size_t r)
{
  r &= 0x7;
  return (uint8_t)(u8 >> r) | (uint8_t)(u8 << (8 - r));
}

uint16_t bit_left_rotation16(uint16_t u16, size_t r)
{
  r &= 0xf;
  return (uint16_t)(u16 >> (16 - r)) | (uint16_t)(u16 << r);
}

uint16_t bit_right_rotation16(uint16_t u16, size_t r)
{
  r &= 0xf;
  return (uint16_t)(u16 >> r) | (uint16_t)(u16 << (16 - r));
}

uint32_t bit_left_rotation32(uint32_t u32, size_t r)
{
  r &= 0x1f;
  return (uint32_t)(u32 >> (32 - r)) | (uint32_t)(u32 << r);
}

uint32_t bit_right_rotation32(uint32_t u32, size_t r)
{
  r &= 0x1f;
  return (uint32_t)(u32 >> r) | (uint32_t)(u32 << (32 - r));
}

uint64_t bit_left_rotation64(uint64_t u64, size_t r)
{
  r &= 0x3f;
  return (uint64_t)(u64 >> (64 - r)) | (uint64_t)(u64 << r);
}

uint64_t bit_right_rotation64(uint64_t u64, size_t r)
{
  r &= 0x3f;
  return (uint64_t)(u64 >> r) | (uint64_t)(u64 << (64 - r));
}

int main(void)
{
  uint8_t u8;
  uint16_t u16;
  uint32_t u32;
  uint64_t u64;
  size_t r;

  printf("Please input an 8-bit unsigned integer: 0x");
  scanf("%hhx", &u8);
  printf("Please input a number of rotations: ");
  scanf("%zu", &r);

  printf(" bit_left_rotation8(0x%02hhx, %zu) = 0x%02hhx\n",
         u8, r, bit_left_rotation8(u8, r));
  printf("bit_right_rotation8(0x%02hhx, %zu) = 0x%02hhx\n",
         u8, r, bit_right_rotation8(u8, r));

  printf("Please input a 16-bit unsigned integer: 0x");
  scanf("%hx", &u16);
  printf("Please input a number of rotations: ");
  scanf("%zu", &r);

  printf(" bit_left_rotation16(0x%04hx, %zu) = 0x%04hx\n",
         u16, r, bit_left_rotation16(u16, r));
  printf("bit_right_rotation16(0x%04hx, %zu) = 0x%04hx\n",
         u16, r, bit_right_rotation16(u16, r));

  printf("Please input a 32-bit unsigned integer: 0x");
  scanf("%x", &u32);
  printf("Please input a number of rotations: ");
  scanf("%zu", &r);

  printf(" bit_left_rotation32(0x%08x, %zu) = 0x%08x\n",
         u32, r, bit_left_rotation32(u32, r));
  printf("bit_right_rotation32(0x%08x, %zu) = 0x%08x\n",
         u32, r, bit_right_rotation32(u32, r));

  printf("Please input a 64-bit unsigned integer: 0x");
  scanf("%lx", &u64);
  printf("Please input a number of rotations: ");
  scanf("%zu", &r);

  printf(" bit_left_rotation64(0x%016lx, %zu) = 0x%016lx\n",
         u64, r, bit_left_rotation64(u64, r));
  printf("bit_right_rotation64(0x%016lx, %zu) = 0x%016lx\n",
         u64, r, bit_right_rotation64(u64, r));

  return 0;
}

100

101

102

103

104

105

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdio.h>

#include <stdint.h>

uint8_t bit_left_rotation8(uint8_t u8, size_t r)

{

r &= 0x7;

return (uint8_t)(u8 >> (8 - r)) | (uint8_t)(u8 << r);

}

uint8_t bit_right_rotation8(uint8_t u8, size_t r)

{

r &= 0x7;

return (uint8_t)(u8 >> r) | (uint8_t)(u8 << (8 - r));

}

uint16_t bit_left_rotation16(uint16_t u16, size_t r)

{

r &= 0xf;

return (uint16_t)(u16 >> (16 - r)) | (uint16_t)(u16 << r);

}

uint16_t bit_right_rotation16(uint16_t u16, size_t r)

{

r &= 0xf;

return (uint16_t)(u16 >> r) | (uint16_t)(u16 << (16 - r));

}

uint32_t bit_left_rotation32(uint32_t u32, size_t r)

{

r &= 0x1f;

return (uint32_t)(u32 >> (32 - r)) | (uint32_t)(u32 << r);

}

uint32_t bit_right_rotation32(uint32_t u32, size_t r)

{

r &= 0x1f;

return (uint32_t)(u32 >> r) | (uint32_t)(u32 << (32 - r));

}

uint64_t bit_left_rotation64(uint64_t u64, size_t r)

{

r &= 0x3f;

return (uint64_t)(u64 >> (64 - r)) | (uint64_t)(u64 << r);

}

uint64_t bit_right_rotation64(uint64_t u64, size_t r)

{

r &= 0x3f;

return (uint64_t)(u64 >> r) | (uint64_t)(u64 << (64 - r));

}

int main(void)

{

uint8_t u8;

uint16_t u16;

uint32_t u32;

uint64_t u64;

size_t r;

printf("Please input an 8-bit unsigned integer: 0x");

scanf("%hhx", &u8);

printf("Please input a number of rotations: ");

scanf("%zu", &r);

printf(" bit_left_rotation8(0x%02hhx, %zu) = 0x%02hhx\n",

u8, r, bit_left_rotation8(u8, r));

printf("bit_right_rotation8(0x%02hhx, %zu) = 0x%02hhx\n",

u8, r, bit_right_rotation8(u8, r));

printf("Please input a 16-bit unsigned integer: 0x");

scanf("%hx", &u16);

printf("Please input a number of rotations: ");

scanf("%zu", &r);

printf(" bit_left_rotation16(0x%04hx, %zu) = 0x%04hx\n",

u16, r, bit_left_rotation16(u16, r));

printf("bit_right_rotation16(0x%04hx, %zu) = 0x%04hx\n",

u16, r, bit_right_rotation16(u16, r));

printf("Please input a 32-bit unsigned integer: 0x");

scanf("%x", &u32);

printf("Please input a number of rotations: ");

scanf("%zu", &r);

printf(" bit_left_rotation32(0x%08x, %zu) = 0x%08x\n",

u32, r, bit_left_rotation32(u32, r));

printf("bit_right_rotation32(0x%08x, %zu) = 0x%08x\n",

u32, r, bit_right_rotation32(u32, r));

printf("Please input a 64-bit unsigned integer: 0x");

scanf("%lx", &u64);

printf("Please input a number of rotations: ");

scanf("%zu", &r);

printf(" bit_left_rotation64(0x%016lx, %zu) = 0x%016lx\n",

u64, r, bit_left_rotation64(u64, r));

printf("bit_right_rotation64(0x%016lx, %zu) = 0x%016lx\n",

u64, r, bit_right_rotation64(u64, r));

return 0;

}

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

$ gcc bit_rotation.c 
$ a.out 
Please input an 8-bit unsigned integer: 0xf0
Please input a number of rotations: 1
bit_left_rotation8(0xf0, 1)  = 0xe1
bit_right_rotation8(0xf0, 1) = 0x78
Please input a 16-bit unsigned integer: 0xf0f0
Please input a number of rotations: 1
bit_left_rotation16(0xf0f0, 1)  = 0xe1e1
bit_right_rotation16(0xf0f0, 1) = 0x7878
Please input a 32-bit unsigned integer: 0xf0f0f0f01
Please input a number of rotations: ^C
$ a.out
Please input a 8-bit unsigned integer: 0xf0
Please input a number of rotations: 1
bit_left_rotation8(0xf0, 1)  = 0xe1
bit_right_rotation8(0xf0, 1) = 0x78
Please input a 16-bit unsigned integer: 0xf0f0
Please input a number of rotations: 1
bit_left_rotation16(0xf0f0, 1)  = 0xe1e1
bit_right_rotation16(0xf0f0, 1) = 0x7878
Please input a 32-bit unsigned integer: 0xf0f0f0f0
Please input a number of rotations: 1
bit_left_rotation32(0xf0f0f0f0, 1)  = 0xe1e1e1e1
bit_right_rotation32(0xf0f0f0f0, 1) = 0x78787878
Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0
Please input a number of rotations: 1
bit_left_rotation64(0xf0f0f0f0f0f0f0f0, 1)  = 0xe1e1e1e1e1e1e1e1
bit_right_rotation64(0xf0f0f0f0f0f0f0f0, 1) = 0x7878787878787878

$ gcc bit_rotation.c

$ a.out

Please input an 8-bit unsigned integer: 0xf0

Please input a number of rotations: 1

bit_left_rotation8(0xf0, 1) = 0xe1

bit_right_rotation8(0xf0, 1) = 0x78

Please input a 16-bit unsigned integer: 0xf0f0

Please input a number of rotations: 1

bit_left_rotation16(0xf0f0, 1) = 0xe1e1

bit_right_rotation16(0xf0f0, 1) = 0x7878

Please input a 32-bit unsigned integer: 0xf0f0f0f01

Please input a number of rotations: ^C

$ a.out

Please input a 8-bit unsigned integer: 0xf0

Please input a number of rotations: 1

bit_left_rotation8(0xf0, 1) = 0xe1

bit_right_rotation8(0xf0, 1) = 0x78

Please input a 16-bit unsigned integer: 0xf0f0

Please input a number of rotations: 1

bit_left_rotation16(0xf0f0, 1) = 0xe1e1

bit_right_rotation16(0xf0f0, 1) = 0x7878

Please input a 32-bit unsigned integer: 0xf0f0f0f0

Please input a number of rotations: 1

bit_left_rotation32(0xf0f0f0f0, 1) = 0xe1e1e1e1

bit_right_rotation32(0xf0f0f0f0, 1) = 0x78787878

Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0

Please input a number of rotations: 1

bit_left_rotation64(0xf0f0f0f0f0f0f0f0, 1) = 0xe1e1e1e1e1e1e1e1

bit_right_rotation64(0xf0f0f0f0f0f0f0f0, 1) = 0x7878787878787878

ビットのセット/クリア

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

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

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

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

bool is_bit_set8(uint8_t *buf, size_t n)
{
  uint8_t mask;

  buf += n >> 3;
  mask = 1 << (n & 0x7);

  if ((*buf & mask) == mask) {
    return true;
  }

  return false;
}

void set_bit8(volatile uint8_t *buf, size_t n)
{
  uint8_t mask;

  buf += n >> 3;
  mask = 1 << (n & 0x7);
  *buf |= mask;
}

void clear_bit8(volatile uint8_t *buf, size_t n)
{
  uint8_t mask;

  buf += n >> 3;
  mask = 1 << (n & 0x7);
  *buf &= ~mask;
}

void change_bit8(volatile uint8_t *buf, size_t n)
{
  uint8_t mask;

  buf += n >> 3;
  mask = 1 << (n & 0x7);
  *buf ^= mask;
}

bool is_bit_set16(uint16_t *buf, size_t n)
{
  uint16_t mask;

  buf += n >> 4;
  mask = 1 << (n & 0xf);

  if ((*buf & mask) == mask) {
    return true;
  }

  return false;
}

void set_bit16(volatile uint16_t *buf, size_t n)
{
  uint16_t mask;

  buf += n >> 4;
  mask = 1 << (n & 0xf);
  *buf |= mask;
}

void clear_bit16(volatile uint16_t *buf, size_t n)
{
  uint16_t mask;

  buf += n >> 4;
  mask = 1 << (n & 0xf);
  *buf &= ~mask;
}

void change_bit16(volatile uint16_t *buf, size_t n)
{
  uint16_t mask;

  buf += n >> 4;
  mask = 1 << (n & 0xf);
  *buf ^= mask;
}

bool is_bit_set32(uint32_t *buf, size_t n)
{
  uint32_t mask;

  buf += n >> 5;
  mask = 1 << (n & 0x1f);

  if ((*buf & mask) == mask) {
    return true;
  }

  return false;
}

void set_bit32(volatile uint32_t *buf, size_t n)
{
  uint32_t mask;

  buf += n >> 5;
  mask = 1 << (n & 0x1f);
  *buf |= mask;
}

void clear_bit32(volatile uint32_t *buf, size_t n)
{
  uint32_t mask;

  buf += n >> 5;
  mask = 1 << (n & 0x1f);
  *buf &= ~mask;
}

void change_bit32(volatile uint32_t *buf, size_t n)
{
  uint32_t mask;

  buf += n >> 5;
  mask = 1 << (n & 0x1f);
  *buf ^= mask;
}

bool is_bit_set64(uint64_t *buf, size_t n)
{
  uint64_t mask;

  buf += n >> 6;
  mask = 1 << (n & 0x3f);

  if ((*buf & mask) == mask) {
    return true;
  }

  return false;
}

void set_bit64(volatile uint64_t *buf, size_t n)
{
  uint64_t mask;

  buf += n >> 6;
  mask = 1 << (n & 0x3f);
  *buf |= mask;
}

void clear_bit64(volatile uint64_t *buf, size_t n)
{
  uint64_t mask;

  buf += n >> 6;
  mask = 1 << (n & 0x3f);
  *buf &= ~mask;
}

void change_bit64(volatile uint64_t *buf, size_t n)
{
  uint64_t mask;

  buf += n >> 6;
  mask = 1 << (n & 0x3f);
  *buf ^= mask;
}

int main(void)
{
  uint8_t u8;
  uint16_t u16;
  uint32_t u32;
  uint64_t u64;
  size_t n;

  printf("Please input an 8-bit unsigned integer: 0x");
  scanf("%hhx", &u8);
  printf("Please input n-th bits to set/clear: ");
  scanf("%zu", &n);

  printf("u8 = %02hhx\n", u8);
  set_bit8(&u8, n);
  printf("u8 = %02hhx\n", u8);

  if (is_bit_set8(&u8, n)) {
    printf("is_bit_set8(%02hhx, %zu) = %d\n", u8, n, is_bit_set8(&u8, n));
  }

  clear_bit8(&u8, n);
  printf("u8 = %02hhx\n", u8);
  change_bit8(&u8, n);
  printf("u8 = %02hhx\n", u8);
  change_bit8(&u8, n);
  printf("u8 = %02hhx\n", u8);

  printf("Please input a 16-bit unsigned integer: 0x");
  scanf("%hx", &u16);
  printf("Please input n-th bits to set/clear: ");
  scanf("%zu", &n);

  printf("u16 = %04hx\n", u16);
  set_bit16(&u16, n);
  printf("u16 = %04hx\n", u16);

  if (is_bit_set16(&u16, n)) {
    printf("is_bit_set16(%04hx, %zu) = %d\n", u16, n, is_bit_set16(&u16, n));
  }

  clear_bit16(&u16, n);
  printf("u16 = %04hx\n", u16);
  change_bit16(&u16, n);
  printf("u16 = %04hx\n", u16);
  change_bit16(&u16, n);
  printf("u16 = %04hx\n", u16);

  printf("Please input a 32-bit unsigned integer: 0x");
  scanf("%x", &u32);
  printf("Please input n-th bits to set/clear: ");
  scanf("%zu", &n);

  printf("u32 = %08x\n", u32);
  set_bit32(&u32, n);
  printf("u32 = %08x\n", u32);

  if (is_bit_set32(&u32, n)) {
    printf("is_bit_set32(%08x, %zu) = %d\n", u32, n, is_bit_set32(&u32, n));
  }

  clear_bit32(&u32, n);
  printf("u32 = %08x\n", u32);
  change_bit32(&u32, n);
  printf("u32 = %08x\n", u32);
  change_bit32(&u32, n);
  printf("u32 = %08x\n", u32);

  printf("Please input a 64-bit unsigned integer: 0x");
  scanf("%lx", &u64);
  printf("Please input n-th bits to set/clear: ");
  scanf("%zu", &n);

  printf("u64 = %016lx\n", u64);
  set_bit64(&u64, n);
  printf("u64 = %016lx\n", u64);

  if (is_bit_set64(&u64, n)) {
    printf("is_bit_set64(%016lx, %zu) = %d\n", u64, n, is_bit_set64(&u64, n));
  }

  clear_bit64(&u64, n);
  printf("u64 = %016lx\n", u64);
  change_bit64(&u64, n);
  printf("u64 = %016lx\n", u64);
  change_bit64(&u64, n);
  printf("u64 = %016lx\n", u64);

  return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdio.h>

#include <stdint.h>

#include <stdbool.h>

bool is_bit_set8(uint8_t *buf, size_t n)

{

uint8_t mask;

buf += n >> 3;

mask = 1 << (n & 0x7);

if ((*buf & mask) == mask) {

return true;

}

return false;

}

void set_bit8(volatile uint8_t *buf, size_t n)

{

uint8_t mask;

buf += n >> 3;

mask = 1 << (n & 0x7);

*buf |= mask;

}

void clear_bit8(volatile uint8_t *buf, size_t n)

{

uint8_t mask;

buf += n >> 3;

mask = 1 << (n & 0x7);

*buf &= ~mask;

}

void change_bit8(volatile uint8_t *buf, size_t n)

{

uint8_t mask;

buf += n >> 3;

mask = 1 << (n & 0x7);

*buf ^= mask;

}

bool is_bit_set16(uint16_t *buf, size_t n)

{

uint16_t mask;

buf += n >> 4;

mask = 1 << (n & 0xf);

if ((*buf & mask) == mask) {

return true;

}

return false;

}

void set_bit16(volatile uint16_t *buf, size_t n)

{

uint16_t mask;

buf += n >> 4;

mask = 1 << (n & 0xf);

*buf |= mask;

}

void clear_bit16(volatile uint16_t *buf, size_t n)

{

uint16_t mask;

buf += n >> 4;

mask = 1 << (n & 0xf);

*buf &= ~mask;

}

void change_bit16(volatile uint16_t *buf, size_t n)

{

uint16_t mask;

buf += n >> 4;

mask = 1 << (n & 0xf);

*buf ^= mask;

}

bool is_bit_set32(uint32_t *buf, size_t n)

{

uint32_t mask;

buf += n >> 5;

mask = 1 << (n & 0x1f);

if ((*buf & mask) == mask) {

return true;

}

return false;

}

void set_bit32(volatile uint32_t *buf, size_t n)

{

uint32_t mask;

buf += n >> 5;

mask = 1 << (n & 0x1f);

*buf |= mask;

}

void clear_bit32(volatile uint32_t *buf, size_t n)

{

uint32_t mask;

buf += n >> 5;

mask = 1 << (n & 0x1f);

*buf &= ~mask;

}

void change_bit32(volatile uint32_t *buf, size_t n)

{

uint32_t mask;

buf += n >> 5;

mask = 1 << (n & 0x1f);

*buf ^= mask;

}

bool is_bit_set64(uint64_t *buf, size_t n)

{

uint64_t mask;

buf += n >> 6;

mask = 1 << (n & 0x3f);

if ((*buf & mask) == mask) {

return true;

}

return false;

}

void set_bit64(volatile uint64_t *buf, size_t n)

{

uint64_t mask;

buf += n >> 6;

mask = 1 << (n & 0x3f);

*buf |= mask;

}

void clear_bit64(volatile uint64_t *buf, size_t n)

{

uint64_t mask;

buf += n >> 6;

mask = 1 << (n & 0x3f);

*buf &= ~mask;

}

void change_bit64(volatile uint64_t *buf, size_t n)

{

uint64_t mask;

buf += n >> 6;

mask = 1 << (n & 0x3f);

*buf ^= mask;

}

int main(void)

{

uint8_t u8;

uint16_t u16;

uint32_t u32;

uint64_t u64;

size_t n;

printf("Please input an 8-bit unsigned integer: 0x");

scanf("%hhx", &u8);

printf("Please input n-th bits to set/clear: ");

scanf("%zu", &n);

printf("u8 = %02hhx\n", u8);

set_bit8(&u8, n);

printf("u8 = %02hhx\n", u8);

if (is_bit_set8(&u8, n)) {

printf("is_bit_set8(%02hhx, %zu) = %d\n", u8, n, is_bit_set8(&u8, n));

}

clear_bit8(&u8, n);

printf("u8 = %02hhx\n", u8);

change_bit8(&u8, n);

printf("u8 = %02hhx\n", u8);

change_bit8(&u8, n);

printf("u8 = %02hhx\n", u8);

printf("Please input a 16-bit unsigned integer: 0x");

scanf("%hx", &u16);

printf("Please input n-th bits to set/clear: ");

scanf("%zu", &n);

printf("u16 = %04hx\n", u16);

set_bit16(&u16, n);

printf("u16 = %04hx\n", u16);

if (is_bit_set16(&u16, n)) {

printf("is_bit_set16(%04hx, %zu) = %d\n", u16, n, is_bit_set16(&u16, n));

}

clear_bit16(&u16, n);

printf("u16 = %04hx\n", u16);

change_bit16(&u16, n);

printf("u16 = %04hx\n", u16);

change_bit16(&u16, n);

printf("u16 = %04hx\n", u16);

printf("Please input a 32-bit unsigned integer: 0x");

scanf("%x", &u32);

printf("Please input n-th bits to set/clear: ");

scanf("%zu", &n);

printf("u32 = %08x\n", u32);

set_bit32(&u32, n);

printf("u32 = %08x\n", u32);

if (is_bit_set32(&u32, n)) {

printf("is_bit_set32(%08x, %zu) = %d\n", u32, n, is_bit_set32(&u32, n));

}

clear_bit32(&u32, n);

printf("u32 = %08x\n", u32);

change_bit32(&u32, n);

printf("u32 = %08x\n", u32);

change_bit32(&u32, n);

printf("u32 = %08x\n", u32);

printf("Please input a 64-bit unsigned integer: 0x");

scanf("%lx", &u64);

printf("Please input n-th bits to set/clear: ");

scanf("%zu", &n);

printf("u64 = %016lx\n", u64);

set_bit64(&u64, n);

printf("u64 = %016lx\n", u64);

if (is_bit_set64(&u64, n)) {

printf("is_bit_set64(%016lx, %zu) = %d\n", u64, n, is_bit_set64(&u64, n));

}

clear_bit64(&u64, n);

printf("u64 = %016lx\n", u64);

change_bit64(&u64, n);

printf("u64 = %016lx\n", u64);

change_bit64(&u64, n);

printf("u64 = %016lx\n", u64);

return 0;

}

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

$ gcc bit_set_and_clear.c
$ a.out
Please input an 8-bit unsigned integer: 0xf0
Please input n-th bits to set/clear: 1
u8 = f0
u8 = f2
is_bit_set8(f2, 1) = 1
u8 = f0
u8 = f2
u8 = f0
Please input a 16-bit unsigned integer: 0xf0f0
Please input n-th bits to set/clear: 1
u16 = f0f0
u16 = f0f2
is_bit_set16(f0f2, 1) = 1
u16 = f0f0
u16 = f0f2
u16 = f0f0
Please input a 32-bit unsigned integer: 0xf0f0f0f0
Please input n-th bits to set/clear: 1
u32 = f0f0f0f0
u32 = f0f0f0f2
is_bit_set32(f0f0f0f2, 1) = 1
u32 = f0f0f0f0
u32 = f0f0f0f2
u32 = f0f0f0f0
Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0
Please input n-th bits to set/clear: 1
u64 = f0f0f0f0f0f0f0f0
u64 = f0f0f0f0f0f0f0f2
is_bit_set64(f0f0f0f0f0f0f0f2, 1) = 1
u64 = f0f0f0f0f0f0f0f0
u64 = f0f0f0f0f0f0f0f2
u64 = f0f0f0f0f0f0f0f0

$ gcc bit_set_and_clear.c

$ a.out

Please input an 8-bit unsigned integer: 0xf0

Please input n-th bits to set/clear: 1

u8 = f0

u8 = f2

is_bit_set8(f2, 1) = 1

u8 = f0

u8 = f2

u8 = f0

Please input a 16-bit unsigned integer: 0xf0f0

Please input n-th bits to set/clear: 1

u16 = f0f0

u16 = f0f2

is_bit_set16(f0f2, 1) = 1

u16 = f0f0

u16 = f0f2

u16 = f0f0

Please input a 32-bit unsigned integer: 0xf0f0f0f0

Please input n-th bits to set/clear: 1

u32 = f0f0f0f0

u32 = f0f0f0f2

is_bit_set32(f0f0f0f2, 1) = 1

u32 = f0f0f0f0

u32 = f0f0f0f2

u32 = f0f0f0f0

Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0

Please input n-th bits to set/clear: 1

u64 = f0f0f0f0f0f0f0f0

u64 = f0f0f0f0f0f0f0f2

is_bit_set64(f0f0f0f0f0f0f0f2, 1) = 1

u64 = f0f0f0f0f0f0f0f0

u64 = f0f0f0f0f0f0f0f2

u64 = f0f0f0f0f0f0f0f0

ビットのスキャン

ビットのスキャンとは，レジスタの中で最も最初にビットがセットされている（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

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

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

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdio.h>
#include <stdint.h>

uint8_t find_first_bit8(uint8_t u8)
{
  uint8_t num = 0;

  if (u8 == 0) {
    return 0;
  }

  if ((u8 & 0xf) == 0) {
    num += 4;
    u8 >>= 4;
  }

  if ((u8 & 0x3) == 0) {
    num += 2;
    u8 >>= 2;
  }

  if ((u8 & 0x1) == 0) {
    num += 1;
  }

  return num;
}

uint8_t find_last_bit8(uint8_t u8)
{
  uint8_t num = 7;

  if (u8 == 0) {
    return 0;
  }

  if (!(u8 & (~0u << 4))) {
    num -= 4;
    u8 <<= 4;
  }

  if (!(u8 & (~0u << 6))) {
    num -= 2;
    u8 <<= 2;
  }

  if (!(u8 & (~0u << 7))) {
    num -= 1;
    u8 <<= 1;
  }

  return num;
}

uint16_t find_first_bit16(uint16_t u16)
{
  uint16_t num = 0;

  if (u16 == 0) {
    return 0;
  }

  if ((u16 & 0xff) == 0) {
    num += 8;
    u16 >>= 8;
  }

  if ((u16 & 0xf) == 0) {
    num += 4;
    u16 >>= 4;
  }

  if ((u16 & 0x3) == 0) {
    num += 2;
    u16 >>= 2;
  }

  if ((u16 & 0x1) == 0) {
    num += 1;
  }

  return num;
}

uint16_t find_last_bit16(uint16_t u16)
{
  uint16_t num = 15;

  if (u16 == 0) {
    return 0;
  }

  if (!(u16 & (~0u << 8))) {
    num -= 8;
    u16 <<= 8;
  }

  if (!(u16 & (~0u << 12))) {
    num -= 4;
    u16 <<= 4;
  }

  if (!(u16 & (~0u << 14))) {
    num -= 2;
    u16 <<= 2;
  }

  if (!(u16 & (~0u << 15))) {
    num -= 1;
    u16 <<= 1;
  }

  return num;
}

uint32_t find_first_bit32(uint32_t u32)
{
  uint32_t num = 0;

  if (u32 == 0) {
    return 0;
  }

  if ((u32 & 0xffff) == 0) {
    num += 16;
    u32 >>= 16;
  }

  if ((u32 & 0xff) == 0) {
    num += 8;
    u32 >>= 8;
  }

  if ((u32 & 0xf) == 0) {
    num += 4;
    u32 >>= 4;
  }

  if ((u32 & 0x3) == 0) {
    num += 2;
    u32 >>= 2;
  }

  if ((u32 & 0x1) == 0) {
    num += 1;
  }

  return num;
}

uint32_t find_last_bit32(uint32_t u32)
{
  uint32_t num = 31;

  if (u32 == 0) {
    return 0;
  }

  if (!(u32 & (~0u << 16))) {
    num -= 16;
    u32 <<= 16;
  }

  if (!(u32 & (~0u << 24))) {
    num -= 8;
    u32 <<= 8;
  }

  if (!(u32 & (~0u << 28))) {
    num -= 4;
    u32 <<= 4;
  }

  if (!(u32 & (~0u << 30))) {
    num -= 2;
    u32 <<= 2;
  }

  if (!(u32 & (~0u << 31))) {
    num -= 1;
  }

  return num;
}

uint64_t find_first_bit64(uint64_t u64)
{
  uint64_t num = 0;

  if (u64 == 0) {
    return 0;
  }

  if ((u64 & 0xffffffffffffffffUL) == 0) {
    num += 64;
    u64 = 0;
  }

  if ((u64 & 0xffffffff) == 0) {
    num += 32;
    u64 >>= 32;
  }

  if ((u64 & 0xffff) == 0) {
    num += 16;
    u64 >>= 16;
  }

  if ((u64 & 0xff) == 0) {
    num += 8;
    u64 >>= 8;
  }

  if ((u64 & 0xf) == 0) {
    num += 4;
    u64 >>= 4;
  }

  if ((u64 & 0x3) == 0) {
    num += 2;
    u64 >>= 2;
  }

  if ((u64 & 0x1) == 0) {
    num += 1;
  }

  return num;
}

uint64_t find_last_bit64(uint64_t u64)
{
  uint64_t num = 63;

  if (u64 == 0) {
    return 0;
  }

  if (!(u64 & (~0ul << 32))) {
    num -= 32;
    u64 <<= 32;
  }

  if (!(u64 & (~0ul << 48))) {
    num -= 16;
    u64 <<= 16;
  }

  if (!(u64 & (~0ul << 56))) {
    num -= 8;
    u64 <<= 8;
  }

  if (!(u64 & (~0ul << 60))) {
    num -= 4;
    u64 <<= 4;
  }

  if (!(u64 & (~0ul << 62))) {
    num -= 2;
    u64 <<= 2;
  }

  if (!(u64 & (~0ul << 63))) {
    num -= 1;
  }

  return num;
}

int main(void)
{
  uint8_t u8;
  uint16_t u16;
  uint32_t u32;
  uint64_t u64;

  printf("Please input an 8-bit unsigned integer: 0x");
  scanf("%hhx", &u8);
  printf("u8 = 0x%02x, find_first_bit8() = %u, find_last_bit8() = %u\n",
         u8, find_first_bit8(u8), find_last_bit8(u8));

  printf("Please input a 16-bit unsigned integer: 0x");
  scanf("%hx", &u16);
  printf("u16 = 0x%04x, find_first_bit16() = %u, find_last_bit16() = %u\n",
         u16, find_first_bit16(u16), find_last_bit16(u16));

  printf("Please input a 32-bit unsigned integer: 0x");
  scanf("%x", &u32);
  printf("u32 = 0x%08x, find_first_bit32() = %u, find_last_bit32() = %u\n",
         u32, find_first_bit32(u32), find_last_bit32(u32));

  printf("Please input a 64-bit unsigned integer: 0x");
  scanf("%lx", &u64);
  printf("u64 = 0x%016lx, find_first_bit64() = %lu, find_last_bit64() = %lu\n",
         u64, find_first_bit64(u64), find_last_bit64(u64));

  return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdio.h>

#include <stdint.h>

uint8_t find_first_bit8(uint8_t u8)

{

uint8_t num = 0;

if (u8 == 0) {

return 0;

}

if ((u8 & 0xf) == 0) {

num += 4;

u8 >>= 4;

}

if ((u8 & 0x3) == 0) {

num += 2;

u8 >>= 2;

}

if ((u8 & 0x1) == 0) {

num += 1;

}

return num;

}

uint8_t find_last_bit8(uint8_t u8)

{

uint8_t num = 7;

if (u8 == 0) {

return 0;

}

if (!(u8 & (~0u << 4))) {

num -= 4;

u8 <<= 4;

}

if (!(u8 & (~0u << 6))) {

num -= 2;

u8 <<= 2;

}

if (!(u8 & (~0u << 7))) {

num -= 1;

u8 <<= 1;

}

return num;

}

uint16_t find_first_bit16(uint16_t u16)

{

uint16_t num = 0;

if (u16 == 0) {

return 0;

}

if ((u16 & 0xff) == 0) {

num += 8;

u16 >>= 8;

}

if ((u16 & 0xf) == 0) {

num += 4;

u16 >>= 4;

}

if ((u16 & 0x3) == 0) {

num += 2;

u16 >>= 2;

}

if ((u16 & 0x1) == 0) {

num += 1;

}

return num;

}

uint16_t find_last_bit16(uint16_t u16)

{

uint16_t num = 15;

if (u16 == 0) {

return 0;

}

if (!(u16 & (~0u << 8))) {

num -= 8;

u16 <<= 8;

}

if (!(u16 & (~0u << 12))) {

num -= 4;

u16 <<= 4;

}

if (!(u16 & (~0u << 14))) {

num -= 2;

u16 <<= 2;

}

if (!(u16 & (~0u << 15))) {

num -= 1;

u16 <<= 1;

}

return num;

}

uint32_t find_first_bit32(uint32_t u32)

{

uint32_t num = 0;

if (u32 == 0) {

return 0;

}

if ((u32 & 0xffff) == 0) {

num += 16;

u32 >>= 16;

}

if ((u32 & 0xff) == 0) {

num += 8;

u32 >>= 8;

}

if ((u32 & 0xf) == 0) {

num += 4;

u32 >>= 4;

}

if ((u32 & 0x3) == 0) {

num += 2;

u32 >>= 2;

}

if ((u32 & 0x1) == 0) {

num += 1;

}

return num;

}

uint32_t find_last_bit32(uint32_t u32)

{

uint32_t num = 31;

if (u32 == 0) {

return 0;

}

if (!(u32 & (~0u << 16))) {

num -= 16;

u32 <<= 16;

}

if (!(u32 & (~0u << 24))) {

num -= 8;

u32 <<= 8;

}

if (!(u32 & (~0u << 28))) {

num -= 4;

u32 <<= 4;

}

if (!(u32 & (~0u << 30))) {

num -= 2;

u32 <<= 2;

}

if (!(u32 & (~0u << 31))) {

num -= 1;

}

return num;

}

uint64_t find_first_bit64(uint64_t u64)

{

uint64_t num = 0;

if (u64 == 0) {

return 0;

}

if ((u64 & 0xffffffffffffffffUL) == 0) {

num += 64;

u64 = 0;

}

if ((u64 & 0xffffffff) == 0) {

num += 32;

u64 >>= 32;

}

if ((u64 & 0xffff) == 0) {

num += 16;

u64 >>= 16;

}

if ((u64 & 0xff) == 0) {

num += 8;

u64 >>= 8;

}

if ((u64 & 0xf) == 0) {

num += 4;

u64 >>= 4;

}

if ((u64 & 0x3) == 0) {

num += 2;

u64 >>= 2;

}

if ((u64 & 0x1) == 0) {

num += 1;

}

return num;

}

uint64_t find_last_bit64(uint64_t u64)

{

uint64_t num = 63;

if (u64 == 0) {

return 0;

}

if (!(u64 & (~0ul << 32))) {

num -= 32;

u64 <<= 32;

}

if (!(u64 & (~0ul << 48))) {

num -= 16;

u64 <<= 16;

}

if (!(u64 & (~0ul << 56))) {

num -= 8;

u64 <<= 8;

}

if (!(u64 & (~0ul << 60))) {

num -= 4;

u64 <<= 4;

}

if (!(u64 & (~0ul << 62))) {

num -= 2;

u64 <<= 2;

}

if (!(u64 & (~0ul << 63))) {

num -= 1;

}

return num;

}

int main(void)

{

uint8_t u8;

uint16_t u16;

uint32_t u32;

uint64_t u64;

printf("Please input an 8-bit unsigned integer: 0x");

scanf("%hhx", &u8);

printf("u8 = 0x%02x, find_first_bit8() = %u, find_last_bit8() = %u\n",

u8, find_first_bit8(u8), find_last_bit8(u8));

printf("Please input a 16-bit unsigned integer: 0x");

scanf("%hx", &u16);

printf("u16 = 0x%04x, find_first_bit16() = %u, find_last_bit16() = %u\n",

u16, find_first_bit16(u16), find_last_bit16(u16));

printf("Please input a 32-bit unsigned integer: 0x");

scanf("%x", &u32);

printf("u32 = 0x%08x, find_first_bit32() = %u, find_last_bit32() = %u\n",

u32, find_first_bit32(u32), find_last_bit32(u32));

printf("Please input a 64-bit unsigned integer: 0x");

scanf("%lx", &u64);

printf("u64 = 0x%016lx, find_first_bit64() = %lu, find_last_bit64() = %lu\n",

u64, find_first_bit64(u64), find_last_bit64(u64));

return 0;

}

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

$ gcc bit_scan.c
$ a.out
Please input an 8-bit unsigned integer: 0xf0
u8 = 0xf0, find_first_bit8() = 4, find_last_bit8() = 7
Please input a 16-bit unsigned integer: 0xf0f0
u16 = 0xf0f0, find_first_bit16() = 4, find_last_bit16() = 15
Please input a 32-bit unsigned integer: 0xf0f0f0f0
u32 = 0xf0f0f0f0, find_first_bit32() = 4, find_last_bit32() = 31
Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0
u64 = 0xf0f0f0f0f0f0f0f0, find_first_bit64() = 4, find_last_bit64() = 63

$ gcc bit_scan.c

$ a.out

Please input an 8-bit unsigned integer: 0xf0

u8 = 0xf0, find_first_bit8() = 4, find_last_bit8() = 7

Please input a 16-bit unsigned integer: 0xf0f0

u16 = 0xf0f0, find_first_bit16() = 4, find_last_bit16() = 15

Please input a 32-bit unsigned integer: 0xf0f0f0f0

u32 = 0xf0f0f0f0, find_first_bit32() = 4, find_last_bit32() = 31

Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0

u64 = 0xf0f0f0f0f0f0f0f0, find_first_bit64() = 4, find_last_bit64() = 63

x86-64のbsf/bsr命令

x86-64のbsf/bsr命令を利用するコードは以下になります．

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

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

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdio.h>
#include <stdint.h>

uint16_t find_first_bit16(uint16_t u16)
{
  uint16_t num;

  asm volatile("bsf %0, %1" : "=r"(num) : "r"(u16));

  return num;
}

uint16_t find_last_bit16(uint16_t u16)
{
  uint16_t num;

  asm volatile("bsr %0, %1" : "=r"(num) : "r"(u16));

  return num;
}

uint32_t find_first_bit32(uint32_t u32)
{
  uint32_t num;

  asm volatile("bsf %0, %1" : "=r"(num) : "r"(u32));

  return num;
}

uint32_t find_last_bit32(uint32_t u32)
{
  uint32_t num;

  asm volatile("bsr %0, %1" : "=r"(num) : "r"(u32));

  return num;
}

uint64_t find_first_bit64(uint64_t u64)
{
  uint64_t num;

  asm volatile("bsf %0, %1" : "=r"(num) : "r"(u64));

  return num;
}

uint64_t find_last_bit64(uint64_t u64)
{
  uint64_t num;

  asm volatile("bsr %0, %1" : "=r"(num) : "r"(u64));

  return num;
}

int main(void)
{
  uint16_t u16;
  uint32_t u32;
  uint64_t u64;

  printf("Please input a 16-bit unsigned integer: 0x");
  scanf("%hx", &u16);
  printf("u16 = 0x%04x, find_first_bit16() = %u, find_last_bit16() = %u\n",
         u16, find_first_bit16(u16), find_last_bit16(u16));

  printf("Please input a 32-bit unsigned integer: 0x");
  scanf("%x", &u32);
  printf("u32 = 0x%08x, find_first_bit32() = %u, find_last_bit32() = %u\n",
         u32, find_first_bit32(u32), find_last_bit32(u32));

  printf("Please input a 64-bit unsigned integer: 0x");
  scanf("%lx", &u64);
  printf("u64 = 0x%016lx, find_first_bit64() = %lu, find_last_bit64() = %lu\n",
         u64, find_first_bit64(u64), find_last_bit64(u64));

  return 0;
}

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdio.h>

#include <stdint.h>

uint16_t find_first_bit16(uint16_t u16)

{

uint16_t num;

asm volatile("bsf %0, %1" : "=r"(num) : "r"(u16));

return num;

}

uint16_t find_last_bit16(uint16_t u16)

{

uint16_t num;

asm volatile("bsr %0, %1" : "=r"(num) : "r"(u16));

return num;

}

uint32_t find_first_bit32(uint32_t u32)

{

uint32_t num;

asm volatile("bsf %0, %1" : "=r"(num) : "r"(u32));

return num;

}

uint32_t find_last_bit32(uint32_t u32)

{

uint32_t num;

asm volatile("bsr %0, %1" : "=r"(num) : "r"(u32));

return num;

}

uint64_t find_first_bit64(uint64_t u64)

{

uint64_t num;

asm volatile("bsf %0, %1" : "=r"(num) : "r"(u64));

return num;

}

uint64_t find_last_bit64(uint64_t u64)

{

uint64_t num;

asm volatile("bsr %0, %1" : "=r"(num) : "r"(u64));

return num;

}

int main(void)

{

uint16_t u16;

uint32_t u32;

uint64_t u64;

printf("Please input a 16-bit unsigned integer: 0x");

scanf("%hx", &u16);

printf("u16 = 0x%04x, find_first_bit16() = %u, find_last_bit16() = %u\n",

u16, find_first_bit16(u16), find_last_bit16(u16));

printf("Please input a 32-bit unsigned integer: 0x");

scanf("%x", &u32);

printf("u32 = 0x%08x, find_first_bit32() = %u, find_last_bit32() = %u\n",

u32, find_first_bit32(u32), find_last_bit32(u32));

printf("Please input a 64-bit unsigned integer: 0x");

scanf("%lx", &u64);

printf("u64 = 0x%016lx, find_first_bit64() = %lu, find_last_bit64() = %lu\n",

u64, find_first_bit64(u64), find_last_bit64(u64));

return 0;

}

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

$ gcc bit_scan_x86_64.c
$ a.out 
Please input a 16-bit unsigned integer: 0xf0f0
u16 = 0xf0f0, find_first_bit16() = 4, find_last_bit16() = 15
Please input a 32-bit unsigned integer: 0xf0f0f0f0
u32 = 0xf0f0f0f0, find_first_bit32() = 4, find_last_bit32() = 31
Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0
u64 = 0xf0f0f0f0f0f0f0f0, find_first_bit64() = 4, find_last_bit64() = 63

$ gcc bit_scan_x86_64.c

$ a.out

Please input a 16-bit unsigned integer: 0xf0f0

u16 = 0xf0f0, find_first_bit16() = 4, find_last_bit16() = 15

Please input a 32-bit unsigned integer: 0xf0f0f0f0

u32 = 0xf0f0f0f0, find_first_bit32() = 4, find_last_bit32() = 31

Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0

u64 = 0xf0f0f0f0f0f0f0f0, find_first_bit64() = 4, find_last_bit64() = 63

ビットのカウント

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

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

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

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

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

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdio.h>
#include <stdint.h>

const size_t NR_BITS[256] = {
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

size_t get_nr_bits8(uint8_t u8)
{
  return NR_BITS[u8];
}

size_t get_nr_leading_zeros8(uint8_t u8)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < 8; i++) {
    if ((u8 & (0x1u << (7 - i))) == 0) {
      num++;
    } else {
      break;
    }
  }

  return num;
}

size_t get_nr_trailing_zeros8(uint8_t u8)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < 8; i++) {
    if ((u8 & (0x1u << i)) == 0) {
      num++;
    } else {
      break;
    }
  }

  return num;
}

size_t get_nr_bits16(uint16_t u16)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < sizeof(uint16_t); i++) {
    num += NR_BITS[((uint8_t *)&u16)[i]];
  }

  return num;
}

size_t get_nr_leading_zeros16(uint16_t u16)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < 16; i++) {
    if ((u16 & (0x1u << (15 - i))) == 0) {
      num++;
    } else {
      break;
    }
  }

  return num;
}

size_t get_nr_trailing_zeros16(uint16_t u16)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < 16; i++) {
    if ((u16 & (0x1u << i)) == 0) {
      num++;
    } else {
      break;
    }
  }

  return num;
}

size_t get_nr_bits32(uint32_t u32)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < sizeof(uint32_t); i++) {
    num += NR_BITS[((uint8_t *)&u32)[i]];
  }

  return num;
}

size_t get_nr_leading_zeros32(uint32_t u32)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < 32; i++) {
    if ((u32 & (0x1u << (31 - i))) == 0) {
      num++;
    } else {
      break;
    }
  }

  return num;
}

size_t get_nr_trailing_zeros32(uint32_t u32)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < 32; i++) {
    if ((u32 & (0x1u << i)) == 0) {
      num++;
    } else {
      break;
    }
  }

  return num;
}

size_t get_nr_bits64(uint64_t u64)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < sizeof(uint64_t); i++) {
    num += NR_BITS[((uint8_t *)&u64)[i]];
  }

  return num;
}

size_t get_nr_leading_zeros64(uint64_t u64)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < 64; i++) {
    if ((u64 & (0x1ul << (63 - i))) == 0) {
      num++;
    } else {
      break;
    }
  }

  return num;
}

size_t get_nr_trailing_zeros64(uint64_t u64)
{
  size_t i;
  size_t num = 0;

  for (i = 0; i < 64; i++) {
    if ((u64 & (0x1ul << i)) == 0) {
      num++;
    } else {
      break;
    }
  }

  return num;
}

int main(void)
{
  uint8_t u8;
  uint16_t u16;
  uint32_t u32;
  uint64_t u64;

  printf("Please input an 8-bit unsigned integer: 0x");
  scanf("%hhx", &u8);
  printf("get_nr_bits8() = %zu\n", get_nr_bits8(u8));
  printf("get_nr_leading_zeros8() = %zu\n", get_nr_leading_zeros8(u8));
  printf("get_nr_trailing_zeros8() = %zu\n", get_nr_trailing_zeros8(u8));

  printf("Please input a 16-bit unsigned integer: 0x");
  scanf("%hx", &u16);
  printf("get_nr_bits16() = %zu\n", get_nr_bits16(u16));
  printf("get_nr_leading_zeros16() = %zu\n", get_nr_leading_zeros16(u16));
  printf("get_nr_trailing_zeros16() = %zu\n", get_nr_trailing_zeros16(u16));

  printf("Please input a 32-bit unsigned integer: 0x");
  scanf("%x", &u32);
  printf("get_nr_bits32() = %zu\n", get_nr_bits32(u32));
  printf("get_nr_leading_zeros32() = %zu\n", get_nr_leading_zeros32(u32));
  printf("get_nr_trailing_zeros32() = %zu\n", get_nr_trailing_zeros32(u32));

  printf("Please input a 64-bit unsigned integer: 0x");
  scanf("%lx", &u64);
  printf("get_nr_bits64() = %zu\n", get_nr_bits64(u64));
  printf("get_nr_leading_zeros64() = %zu\n", get_nr_leading_zeros64(u64));
  printf("get_nr_trailing_zeros64() = %zu\n", get_nr_trailing_zeros64(u64));

  return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdio.h>

#include <stdint.h>

const size_t NR_BITS[256] = {

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,

3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,

4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,

};

size_t get_nr_bits8(uint8_t u8)

{

return NR_BITS[u8];

}

size_t get_nr_leading_zeros8(uint8_t u8)

{

size_t i;

size_t num = 0;

for (i = 0; i < 8; i++) {

if ((u8 & (0x1u << (7 - i))) == 0) {

num++;

} else {

break;

}

return num;

}

size_t get_nr_trailing_zeros8(uint8_t u8)

{

size_t i;

size_t num = 0;

for (i = 0; i < 8; i++) {

if ((u8 & (0x1u << i)) == 0) {

num++;

} else {

break;

}

return num;

}

size_t get_nr_bits16(uint16_t u16)

{

size_t i;

size_t num = 0;

for (i = 0; i < sizeof(uint16_t); i++) {

num += NR_BITS[((uint8_t *)&u16)[i]];

}

return num;

}

size_t get_nr_leading_zeros16(uint16_t u16)

{

size_t i;

size_t num = 0;

for (i = 0; i < 16; i++) {

if ((u16 & (0x1u << (15 - i))) == 0) {

num++;

} else {

break;

}

return num;

}

size_t get_nr_trailing_zeros16(uint16_t u16)

{

size_t i;

size_t num = 0;

for (i = 0; i < 16; i++) {

if ((u16 & (0x1u << i)) == 0) {

num++;

} else {

break;

}

return num;

}

size_t get_nr_bits32(uint32_t u32)

{

size_t i;

size_t num = 0;

for (i = 0; i < sizeof(uint32_t); i++) {

num += NR_BITS[((uint8_t *)&u32)[i]];

}

return num;

}

size_t get_nr_leading_zeros32(uint32_t u32)

{

size_t i;

size_t num = 0;

for (i = 0; i < 32; i++) {

if ((u32 & (0x1u << (31 - i))) == 0) {

num++;

} else {

break;

}

return num;

}

size_t get_nr_trailing_zeros32(uint32_t u32)

{

size_t i;

size_t num = 0;

for (i = 0; i < 32; i++) {

if ((u32 & (0x1u << i)) == 0) {

num++;

} else {

break;

}

return num;

}

size_t get_nr_bits64(uint64_t u64)

{

size_t i;

size_t num = 0;

for (i = 0; i < sizeof(uint64_t); i++) {

num += NR_BITS[((uint8_t *)&u64)[i]];

}

return num;

}

size_t get_nr_leading_zeros64(uint64_t u64)

{

size_t i;

size_t num = 0;

for (i = 0; i < 64; i++) {

if ((u64 & (0x1ul << (63 - i))) == 0) {

num++;

} else {

break;

}

return num;

}

size_t get_nr_trailing_zeros64(uint64_t u64)

{

size_t i;

size_t num = 0;

for (i = 0; i < 64; i++) {

if ((u64 & (0x1ul << i)) == 0) {

num++;

} else {

break;

}

return num;

}

int main(void)

{

uint8_t u8;

uint16_t u16;

uint32_t u32;

uint64_t u64;

printf("Please input an 8-bit unsigned integer: 0x");

scanf("%hhx", &u8);

printf("get_nr_bits8() = %zu\n", get_nr_bits8(u8));

printf("get_nr_leading_zeros8() = %zu\n", get_nr_leading_zeros8(u8));

printf("get_nr_trailing_zeros8() = %zu\n", get_nr_trailing_zeros8(u8));

printf("Please input a 16-bit unsigned integer: 0x");

scanf("%hx", &u16);

printf("get_nr_bits16() = %zu\n", get_nr_bits16(u16));

printf("get_nr_leading_zeros16() = %zu\n", get_nr_leading_zeros16(u16));

printf("get_nr_trailing_zeros16() = %zu\n", get_nr_trailing_zeros16(u16));

printf("Please input a 32-bit unsigned integer: 0x");

scanf("%x", &u32);

printf("get_nr_bits32() = %zu\n", get_nr_bits32(u32));

printf("get_nr_leading_zeros32() = %zu\n", get_nr_leading_zeros32(u32));

printf("get_nr_trailing_zeros32() = %zu\n", get_nr_trailing_zeros32(u32));

printf("Please input a 64-bit unsigned integer: 0x");

scanf("%lx", &u64);

printf("get_nr_bits64() = %zu\n", get_nr_bits64(u64));

printf("get_nr_leading_zeros64() = %zu\n", get_nr_leading_zeros64(u64));

printf("get_nr_trailing_zeros64() = %zu\n", get_nr_trailing_zeros64(u64));

return 0;

}

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

$ gcc bit_count.c
$ a.out 
Please input an 8-bit unsigned integer: 0xf0
get_nr_bits8() = 4
get_nr_leading_zeros8() = 0
get_nr_trailing_zeros8() = 4
Please input a 16-bit unsigned integer: 0xf0f0    
get_nr_bits16() = 8
get_nr_leading_zeros16() = 0
get_nr_trailing_zeros16() = 4
Please input a 32-bit unsigned integer: 0xf0f0f0f0
get_nr_bits32() = 16
get_nr_leading_zeros32() = 0
get_nr_trailing_zeros32() = 4
Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0
get_nr_bits64() = 32
get_nr_leading_zeros64() = 0
get_nr_trailing_zeros64() = 4

$ gcc bit_count.c

$ a.out

Please input an 8-bit unsigned integer: 0xf0

get_nr_bits8() = 4

get_nr_leading_zeros8() = 0

get_nr_trailing_zeros8() = 4

Please input a 16-bit unsigned integer: 0xf0f0

get_nr_bits16() = 8

get_nr_leading_zeros16() = 0

get_nr_trailing_zeros16() = 4

Please input a 32-bit unsigned integer: 0xf0f0f0f0

get_nr_bits32() = 16

get_nr_leading_zeros32() = 0

get_nr_trailing_zeros32() = 4

Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0

get_nr_bits64() = 32

get_nr_leading_zeros64() = 0

get_nr_trailing_zeros64() = 4

x86-64のpopcnt/tzcnt/lzcnt命令

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

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

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

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdio.h>
#include <stdint.h>

size_t get_nr_bits16(uint16_t u16)
{
  uint16_t num;

  asm volatile("popcnt %0, %1" : "=r"(num) : "r"(u16));

  return num;
}

size_t get_nr_leading_zeros16(uint16_t u16)
{
  uint16_t num;

  asm volatile("lzcnt %0, %1" : "=r"(num) : "r"(u16));

  return num;
}

size_t get_nr_trailing_zeros16(uint16_t u16)
{
  uint16_t num;

  asm volatile("tzcnt %0, %1" : "=r"(num) : "r"(u16));

  return num;
}

size_t get_nr_bits32(uint32_t u32)
{
  uint32_t num;

  asm volatile("popcnt %0, %1" : "=r"(num) : "r"(u32));

  return num;
}

size_t get_nr_leading_zeros32(uint32_t u32)
{
  uint32_t num;

  asm volatile("lzcnt %0, %1" : "=r"(num) : "r"(u32));

  return num;
}

size_t get_nr_trailing_zeros32(uint32_t u32)
{
  uint32_t num;

  asm volatile("tzcnt %0, %1" : "=r"(num) : "r"(u32));

  return num;
}

size_t get_nr_bits64(uint64_t u64)
{
  uint64_t num;

  asm volatile("popcnt %0, %1" : "=r"(num) : "r"(u64));

  return num;
}

size_t get_nr_leading_zeros64(uint64_t u64)
{
  uint64_t num;

  asm volatile("lzcnt %0, %1" : "=r"(num) : "r"(u64));

  return num;
}

size_t get_nr_trailing_zeros64(uint64_t u64)
{
  uint64_t num;

  asm volatile("tzcnt %0, %1" : "=r"(num) : "r"(u64));

  return num;
}

int main(void)
{
  uint16_t u16;
  uint32_t u32;
  uint64_t u64;

  printf("Please input a 16-bit unsigned integer: 0x");
  scanf("%hx", &u16);
  printf("get_nr_bits16() = %zu\n", get_nr_bits16(u16));
  printf("get_nr_leading_zeros16() = %zu\n", get_nr_leading_zeros16(u16));
  printf("get_nr_trailing_zeros16() = %zu\n", get_nr_trailing_zeros16(u16));

  printf("Please input a 32-bit unsigned integer: 0x");
  scanf("%x", &u32);
  printf("get_nr_bits32() = %zu\n", get_nr_bits32(u32));
  printf("get_nr_leading_zeros32() = %zu\n", get_nr_leading_zeros32(u32));
  printf("get_nr_trailing_zeros32() = %zu\n", get_nr_trailing_zeros32(u32));

  printf("Please input a 64-bit unsigned integer: 0x");
  scanf("%lx", &u64);
  printf("get_nr_bits64() = %zu\n", get_nr_bits64(u64));
  printf("get_nr_leading_zeros64() = %zu\n", get_nr_leading_zeros64(u64));
  printf("get_nr_trailing_zeros64() = %zu\n", get_nr_trailing_zeros64(u64));

  return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdio.h>

#include <stdint.h>

size_t get_nr_bits16(uint16_t u16)

{

uint16_t num;

asm volatile("popcnt %0, %1" : "=r"(num) : "r"(u16));

return num;

}

size_t get_nr_leading_zeros16(uint16_t u16)

{

uint16_t num;

asm volatile("lzcnt %0, %1" : "=r"(num) : "r"(u16));

return num;

}

size_t get_nr_trailing_zeros16(uint16_t u16)

{

uint16_t num;

asm volatile("tzcnt %0, %1" : "=r"(num) : "r"(u16));

return num;

}

size_t get_nr_bits32(uint32_t u32)

{

uint32_t num;

asm volatile("popcnt %0, %1" : "=r"(num) : "r"(u32));

return num;

}

size_t get_nr_leading_zeros32(uint32_t u32)

{

uint32_t num;

asm volatile("lzcnt %0, %1" : "=r"(num) : "r"(u32));

return num;

}

size_t get_nr_trailing_zeros32(uint32_t u32)

{

uint32_t num;

asm volatile("tzcnt %0, %1" : "=r"(num) : "r"(u32));

return num;

}

size_t get_nr_bits64(uint64_t u64)

{

uint64_t num;

asm volatile("popcnt %0, %1" : "=r"(num) : "r"(u64));

return num;

}

size_t get_nr_leading_zeros64(uint64_t u64)

{

uint64_t num;

asm volatile("lzcnt %0, %1" : "=r"(num) : "r"(u64));

return num;

}

size_t get_nr_trailing_zeros64(uint64_t u64)

{

uint64_t num;

asm volatile("tzcnt %0, %1" : "=r"(num) : "r"(u64));

return num;

}

int main(void)

{

uint16_t u16;

uint32_t u32;

uint64_t u64;

printf("Please input a 16-bit unsigned integer: 0x");

scanf("%hx", &u16);

printf("get_nr_bits16() = %zu\n", get_nr_bits16(u16));

printf("get_nr_leading_zeros16() = %zu\n", get_nr_leading_zeros16(u16));

printf("get_nr_trailing_zeros16() = %zu\n", get_nr_trailing_zeros16(u16));

printf("Please input a 32-bit unsigned integer: 0x");

scanf("%x", &u32);

printf("get_nr_bits32() = %zu\n", get_nr_bits32(u32));

printf("get_nr_leading_zeros32() = %zu\n", get_nr_leading_zeros32(u32));

printf("get_nr_trailing_zeros32() = %zu\n", get_nr_trailing_zeros32(u32));

printf("Please input a 64-bit unsigned integer: 0x");

scanf("%lx", &u64);

printf("get_nr_bits64() = %zu\n", get_nr_bits64(u64));

printf("get_nr_leading_zeros64() = %zu\n", get_nr_leading_zeros64(u64));

printf("get_nr_trailing_zeros64() = %zu\n", get_nr_trailing_zeros64(u64));

return 0;

}

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

$ gcc bit_count_x86_64.c
$ a.out 
Please input a 16-bit unsigned integer: 0xf0f0
get_nr_bits16() = 8
get_nr_leading_zeros16() = 0
get_nr_trailing_zeros16() = 4
Please input a 32-bit unsigned integer: 0xf0f0f0f0
get_nr_bits32() = 16
get_nr_leading_zeros32() = 0
get_nr_trailing_zeros32() = 4
Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0
get_nr_bits64() = 32
get_nr_leading_zeros64() = 0
get_nr_trailing_zeros64() = 4

$ gcc bit_count_x86_64.c

$ a.out

Please input a 16-bit unsigned integer: 0xf0f0

get_nr_bits16() = 8

get_nr_leading_zeros16() = 0

get_nr_trailing_zeros16() = 4

Please input a 32-bit unsigned integer: 0xf0f0f0f0

get_nr_bits32() = 16

get_nr_leading_zeros32() = 0

get_nr_trailing_zeros32() = 4

Please input a 64-bit unsigned integer: 0xf0f0f0f0f0f0f0f0

get_nr_bits64() = 32

get_nr_leading_zeros64() = 0

get_nr_trailing_zeros64() = 4

ARM64（AARCH64）のclz命令

ARM64（AARCH64）のclz命令を利用するコードは以下になります．

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

/*
 * Author: Hiroyuki Chishiro
 * License: 2-Clause BSD
 */
#include <stdio.h>
#include <stdint.h>

size_t get_nr_leading_zeros64(uint64_t u64)
{
  uint64_t num;

  asm volatile("clz %0, %1" : "=r"(num) : "r"(u64));

  return num;
}

int main(void)
{
  uint64_t u64;

  printf("Please input a 64-bit unsigned integer: 0x");
  scanf("%lx", &u64);
  printf("get_nr_leading_zeros64() = %zu\n", get_nr_leading_zeros64(u64));

  return 0;
}

* Author: Hiroyuki Chishiro

* License: 2-Clause BSD

#include <stdio.h>

#include <stdint.h>

size_t get_nr_leading_zeros64(uint64_t u64)

{

uint64_t num;

asm volatile("clz %0, %1" : "=r"(num) : "r"(u64));

return num;

}

int main(void)

{

uint64_t u64;

printf("Please input a 64-bit unsigned integer: 0x");

scanf("%lx", &u64);

printf("get_nr_leading_zeros64() = %zu\n", get_nr_leading_zeros64(u64));

return 0;

}

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

: 【C言語】Raspberry Pi 3のユーザモードとカーネルモードでプログラミング【QEMUを利用】

こういった悩みにお答えします．こういった私から学べます． Raspberry Pi 3（ラズパイ3） Raspberry Pi 3（ラズパイ3）とは，イギリスのラズベリーパイ財団により開発されている ...

続きを見る

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

$ aarch64-linux-gnu-gcc bit_count_arm64.c
$ a.out
Please input a 64-bit unsigned integer: 0x0
get_nr_leading_zeros64() = 64

$ aarch64-linux-gnu-gcc bit_count_arm64.c

$ a.out

Please input a 64-bit unsigned integer: 0x0

get_nr_leading_zeros64() = 64

まとめ

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

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

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

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

私のキャパシティもあり，一定数に達したら終了しますので，今すぐ追加しましょう！

: 元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

こういった悩みにお答えします．こういった私が解説していきます．私が大学の授業で初めてC言語を勉強した時は全然できませんでしたが，先生やTA，友人に相談しながら一生懸命C言語を勉強してできるようにな ...

続きを見る

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

元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社

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

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

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

ビットの回転

ビットのセット/クリア

ビットのスキャン

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

x86-64のbsf/bsr命令

ビットのカウント

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

x86-64のpopcnt/tzcnt/lzcnt命令

ARM64（AARCH64）のclz命令

【C言語】Raspberry Pi 3のユーザモードとカーネルモードでプログラミング【QEMUを利用】

まとめ

元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社