何番目のbitが1であるかを求める速いアルゴリズム

Question

右から何番目のbitが1であるかを求める速いアルゴリズムを探しています。

自分なりに組んでみましたがもっと速い手法がありそうな感じがします。(0番始まりとして値を返しています)

	public static uint Do(uint value)
	{
		uint count = 0;
		if (value == 0)
			return 0;

		while ((value & 1) == 0)
		{
			value >>= 1;
			count++;
		}
		return count;
	}

特に、bit演算をいい感じに用いればwhileで回さなくても求めることができそうなのですが、もしご存じの方がいらっしゃれば教えていただきたいです。

Answer 1

こちらのような、ハッシュテーブルとビット演算を組み合わせた手法があります。

Comments

[rtag]

初めて知りました！ありがとうございます！