前提・実現したいこと
c言語もしくはcppもしくはcudaで
32bitのunsigned int の変数があった時,一番下位の1が立っているbitの桁を返す方法はありますか?(32回ループするforやwhileなどを使う方法以外でお願いします)
例:11101011110101101111110000000000 ならば11桁目が1なので11を返す
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答8件
0
これは「count trailing zeros」と呼ばれる処理です(1ずれるが)。この名で検索するとよいです。
Wikipediaにはde Bruijn sequencesで作ったminimal perfect hash functionを使った乗算1回とビット演算少々+テーブル引きという恐ろしいものがありますね。
https://en.wikipedia.org/wiki/Find_first_set#CTZ
あとCPUによっては1命令でできることもあります。
投稿2019/06/20 00:41
総合スコア3047
0
gccなら__builtin_clz関数を、Visual C++なら_BitScanForward関数を使えば出来そうです。
CUDAでのやり方は分かりません。すいません。
gcc で _BitScanForward & _BitScanReverse 互換関数、MSVC で __builtin_clz & __builtin_ctz 互換関数
投稿2019/06/19 18:22
総合スコア298
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
動作デモ:https://wandbox.org/permlink/vXFGRr1l43jOKb0c(C++コードですが、アルゴリズムはC言語でも動きます)
C++
1#include <cstdint> 2#include <cstdio> 3 4static const int MultiplyDeBruijnBitPosition2[32] = 5{ 6 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 7 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 8}; 9 10int main() 11{ 12 uint32_t n = 0b1110'1011'1101'0110'1111'1100'0000'0000; 13 14 // http://graphics.stanford.edu/~seander/bithacks.html 15 uint32_t v = (n & -n); 16 n = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27]; 17 printf("index: %d\n", n); 18}
注:0-basedのため上記コードは 10 を出力します。11が欲しければ +1 してください;P
投稿2019/06/20 04:14
編集2019/06/20 04:18総合スコア6189
0
以下のサイトが参考になります。
投稿2019/06/20 08:01
総合スコア3579
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
参考情報
- c – 設定されている最下位ビットの位置
https://codeday.me/jp/qa/20181203/34198.html
google で
"c" 最下位ビット
で検索すると、他にもいろいろ情報をえられると思います。
追記
英語サイトも記しておきます。
- Position of least significant bit that is set
投稿2019/06/19 22:18
編集2019/06/21 22:39総合スコア22324
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/06/20 00:37
0
C
1#include <stdio.h> 2#include <math.h> 3 4int lastBitPos(unsigned x) { return x ? (int)log2(x-1 ^ x) + 1 : 0; } 5 6int main(void) { printf("%d\n", lastBitPos(0xebd6fc00)); }
1 がない場合 0 を返します。
[追記]
log2(x-1 ^ x) は log2(-x & x) でも構いません。
投稿2019/06/19 21:48
編集2019/06/20 03:03総合スコア8224
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
自前で論理を組む前提なら
C
1// intが32bitと仮定 2int positionOfLowestBit(int i) { 3 static char tbl[256] = { 8, 0, 1, 0, 2, ... }; 4 int n = 0; 5 if (!(i & 0xFFFF)) { 6 n += 16; 7 i >>= 16; 8 } 9 if (!(i & 0xFF)) { 10 n += 8; 11 i >>= 8; 12 } 13 return n + tbl[i & 0xFF]; 14} 15
こういう類の計算論理をテーブルルックアップに置き換えると単純化できる場合があるという例です。テーブルサイズをあまり大きくするとキャッシュミスがおきやすくなるのでそこそこのサイズにおさめておく配慮も必要と思います。
実用上はrtr1950xさん回答のように既存の機能を利用するのがよいと思いますがこうした論理を考えてみることでアルゴリズムの応用力がつく気がするので学習目的なら自前で実装を考えることは無駄ではないと思います。
追記:質問意図とはちょっと外れますが・・・
他の方の回答と同様、上の論理も0ベース(一番右にあるときを0ビット目とする)を想定してます。どちらかといえば1ベースではなく0ベースで論理を考える機会が多いと思います。その方が都合がよいケースが多いからです。例えばnビット目から始めてmビット目・・・といった論理を考えるとき、1ベースだと結果の位置はn+m-1になりますが、0ベースならn+mとできます。複雑な論理になればなるほど0ベースの方が直感的に分かり易い論理にできるといえましょう。
投稿2019/06/19 18:34
編集2019/06/20 13:18総合スコア18392
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/06/20 02:57
2019/06/20 04:28
0
こんにちは。
forやwhileやgotoを使わないでループを回す場合、再帰関数を使うこともよくあります。(あまり多くは繰り返しできませんが。)
C++
1#include <iostream> 2#include <cstdint> 3 4int count0(uint32_t x, int count=1) 5{ 6 if (x & 1) 7 return count; 8 return count0(x/2, count+1); 9} 10 11int main() 12{ 13 std::cout << count0(0b11101011110101101111110000000000) << "\n"; 14}
投稿2019/06/19 18:05
総合スコア23272
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。