回答編集履歴
3
refinement
test
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
動作デモ：[https://wandbox.org/permlink/
|
|
1
|
+
動作デモ：[https://wandbox.org/permlink/vXFGRr1l43jOKb0c](https://wandbox.org/permlink/vXFGRr1l43jOKb0c)（C++コードですが、アルゴリズムはC言語でも動きます）
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
@@ -10,13 +10,13 @@
|
|
|
10
10
|
|
|
11
11
|
|
|
12
12
|
|
|
13
|
-
static const int MultiplyDeBruijnBitPosition[32] =
|
|
13
|
+
static const int MultiplyDeBruijnBitPosition2[32] =
|
|
14
14
|
|
|
15
15
|
{
|
|
16
16
|
|
|
17
|
-
0,
|
|
17
|
+
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
|
|
18
18
|
|
|
19
|
-
|
|
19
|
+
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
|
|
20
20
|
|
|
21
21
|
};
|
|
22
22
|
|
|
@@ -34,17 +34,7 @@
|
|
|
34
34
|
|
|
35
35
|
uint32_t v = (n & -n);
|
|
36
36
|
|
|
37
|
-
v |= v >> 1;
|
|
38
|
-
|
|
39
|
-
v |= v >> 2;
|
|
40
|
-
|
|
41
|
-
v |= v >> 4;
|
|
42
|
-
|
|
43
|
-
v |= v >> 8;
|
|
44
|
-
|
|
45
|
-
v |= v >> 16;
|
|
46
|
-
|
|
47
|
-
n = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C
|
|
37
|
+
n = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];
|
|
48
38
|
|
|
49
39
|
printf("index: %d\n", n);
|
|
50
40
|
|
2
update
test
CHANGED
|
@@ -51,3 +51,5 @@
|
|
|
51
51
|
}
|
|
52
52
|
|
|
53
53
|
```
|
|
54
|
+
|
|
55
|
+
注：0-basedのため上記コードは 10 を出力します。11が欲しければ +1 してください;P
|
1
update
test
CHANGED
|
@@ -1,3 +1,7 @@
|
|
|
1
|
+
動作デモ：[https://wandbox.org/permlink/VulpWgrC8TC1MJLr](https://wandbox.org/permlink/VulpWgrC8TC1MJLr)（C++コードですが、アルゴリズムはC言語でも動きます）
|
|
2
|
+
|
|
3
|
+
|
|
4
|
+
|
|
1
5
|
```C++
|
|
2
6
|
|
|
3
7
|
#include <cstdint>
|