回答編集履歴
3
refinement
answer
CHANGED
|
@@ -1,13 +1,13 @@
|
|
|
1
|
-
動作デモ：[https://wandbox.org/permlink/
|
|
1
|
+
動作デモ：[https://wandbox.org/permlink/vXFGRr1l43jOKb0c](https://wandbox.org/permlink/vXFGRr1l43jOKb0c)（C++コードですが、アルゴリズムはC言語でも動きます）
|
|
2
2
|
|
|
3
3
|
```C++
|
|
4
4
|
#include <cstdint>
|
|
5
5
|
#include <cstdio>
|
|
6
6
|
|
|
7
|
-
static const int
|
|
7
|
+
static const int MultiplyDeBruijnBitPosition2[32] =
|
|
8
8
|
{
|
|
9
|
-
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
|
|
10
|
-
|
|
9
|
+
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
|
|
10
|
+
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
|
|
11
11
|
};
|
|
12
12
|
|
|
13
13
|
int main()
|
|
@@ -16,12 +16,7 @@
|
|
|
16
16
|
|
|
17
17
|
// http://graphics.stanford.edu/~seander/bithacks.html
|
|
18
18
|
uint32_t v = (n & -n);
|
|
19
|
-
v |= v >> 1;
|
|
20
|
-
v |= v >> 2;
|
|
21
|
-
v |= v >> 4;
|
|
22
|
-
v |= v >> 8;
|
|
23
|
-
v |= v >> 16;
|
|
24
|
-
n =
|
|
19
|
+
n = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];
|
|
25
20
|
printf("index: %d\n", n);
|
|
26
21
|
}
|
|
27
22
|
```
|
2
update
answer
CHANGED
|
@@ -24,4 +24,5 @@
|
|
|
24
24
|
n = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
|
|
25
25
|
printf("index: %d\n", n);
|
|
26
26
|
}
|
|
27
|
-
```
|
|
27
|
+
```
|
|
28
|
+
注：0-basedのため上記コードは 10 を出力します。11が欲しければ +1 してください;P
|
1
update
answer
CHANGED
|
@@ -1,3 +1,5 @@
|
|
|
1
|
+
動作デモ：[https://wandbox.org/permlink/VulpWgrC8TC1MJLr](https://wandbox.org/permlink/VulpWgrC8TC1MJLr)（C++コードですが、アルゴリズムはC言語でも動きます）
|
|
2
|
+
|
|
1
3
|
```C++
|
|
2
4
|
#include <cstdint>
|
|
3
5
|
#include <cstdio>
|