質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

CUDA

CUDAは並列計算プラットフォームであり、Nvidia GPU(Graphics Processing Units)向けのプログラミングモデルです。CUDAは様々なプログラミング言語、ライブラリ、APIを通してNvidiaにインターフェイスを提供します。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

8回答

1540閲覧

c言語で forを使わず32bitの1が立っている最下位bit桁が何番目かを返す方法ありますか?

pypy7

総合スコア15

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

CUDA

CUDAは並列計算プラットフォームであり、Nvidia GPU(Graphics Processing Units)向けのプログラミングモデルです。CUDAは様々なプログラミング言語、ライブラリ、APIを通してNvidiaにインターフェイスを提供します。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2019/06/19 17:22

前提・実現したいこと

c言語もしくはcppもしくはcudaで
32bitのunsigned int の変数があった時,一番下位の1が立っているbitの桁を返す方法はありますか?(32回ループするforやwhileなどを使う方法以外でお願いします)

例:11101011110101101111110000000000 ならば11桁目が1なので11を返す

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答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

ikadzuchi

総合スコア3047

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

gccなら__builtin_clz関数を、Visual C++なら_BitScanForward関数を使えば出来そうです。
CUDAでのやり方は分かりません。すいません。

gcc で _BitScanForward & _BitScanReverse 互換関数、MSVC で __builtin_clz & __builtin_ctz 互換関数

投稿2019/06/19 18:22

rtr1950x

総合スコア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
yohhoy

総合スコア6189

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

KSwordOfHaste

2019/06/20 04:40

これは面白いですね。ikadzuchiさん回答にある方法もそうですが、一見してすぐにピンとこないところに心惹かれます! ちなみにnが0のとき結果が0なのでctz % 32を返す論理ということになるのでしょうか?
yohhoy

2019/06/20 10:13

n==0 のケースは別途チェックしたほうがよさそうですね...
guest

0

以下のサイトが参考になります。

ビットを数える・探すアルゴリズム

投稿2019/06/20 08:01

PineMatsu

総合スコア3579

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

参考情報

  • c – 設定されている最下位ビットの位置

https://codeday.me/jp/qa/20181203/34198.html

google で
"c" 最下位ビット
で検索すると、他にもいろいろ情報をえられると思います。

追記
英語サイトも記しておきます。

  • Position of least significant bit that is set

https://stackoverflow.com/questions/757059/

投稿2019/06/19 22:18

編集2019/06/21 22:39
katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

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
kazuma-s

総合スコア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
KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kazuma-s

2019/06/20 02:57

テーブルの中身を 256個書くのは大変ですが、 次のようにマクロで書けます。 #define T3(x) x+2,0,1,0 #define T2(x) T3(x+2),T3(0),T3(1),T3(0) #define T(x) T2(x+2),T2(0),T2(1),T2(0) static char tbl[256] = { T(2),T(0),T(1),T(0) };
KSwordOfHaste

2019/06/20 04:28

大変なので実際に書く際にはそうした工夫を考えるとよいですね! 自分は比較的簡単な考え方の例を挙げましたが、テーブルの中身は自明に近いのであまり注意を払いませんでした w;
guest

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}

wandbox
2進数リテラル

投稿2019/06/19 18:05

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問