teratail
回答率
85.30%
teratail header banner
teratail header banner
質問するログイン新規登録
トップCに関する質問ビット列のカウント、比較方法について

編集履歴

回答編集履歴

8

表検索による高速版のコードを追加

2020/09/16 01:52

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -118,4 +118,48 @@
118
118
  ```
119
119
  演算回数
120
120
  (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
121
- (2) = 4回、| 1回、>> 6回、& 7回、+ 4回
121
+ (2) = 4回、| 1回、>> 6回、& 7回、+ 4回
122
+
123
+ **追記3**
124
+ 表検索のため演算回数が少ない高速版
125
+ ```C++
126
+ #include <iostream>
127
+
128
+ #define A3(x) x,x+1,x+2,x+3,x+4,x+5,x+6,x+7
129
+ #define A6(x) A3(x),A3(x+1),A3(x+2),A3(x+3),A3(x+4),A3(x+5),A3(x+6),A3(x+7)
130
+ #define A9(x) A6(x),A6(x+1),A6(x+2),A6(x+3),A6(x+4),A6(x+5),A6(x+6),A6(x+7)
131
+ char a[512] = { A9(0) };
132
+
133
+ #define B3(x) x,x+1,x+1,x+1,x+1,x+1,x+1,x+1
134
+ #define B6(x) B3(x),B3(x+1),B3(x+1),B3(x+1),B3(x+1),B3(x+1),B3(x+1),B3(x+1)
135
+ #define B9(x) B6(x),B6(x+1),B6(x+1),B6(x+1),B6(x+1),B6(x+1),B6(x+1),B6(x+1)
136
+ char b[512] = { B9(0) };
137
+
138
+ #define C3(x) x,x,x+1,x+1,x+1,x+1,x+1,x+1
139
+ #define C6(x) C3(x),C3(x),C3(x+1),C3(x+1),C3(x+1),C3(x+1),C3(x+1),C3(x+1)
140
+ #define C9(x) C6(x),C6(x),C6(x+1),C6(x+1),C6(x+1),C6(x+1),C6(x+1),C6(x+1)
141
+ char c[512] = { C9(0) };
142
+
143
+ #define D3(x) x,x,x+1,x,x,x,x,x
144
+ #define D6(x) D3(x),D3(x),D3(x+1),D3(x),D3(x),D3(x),D3(x),D3(x)
145
+ #define D9(x) D6(x),D6(x),D6(x+1),D6(x),D6(x),D6(x),D6(x),D6(x)
146
+ char d[512] = { D9(0) };
147
+
148
+ int main()
149
+ {
150
+ int x = 69510160;
151
+ int cnt;
152
+
153
+ cnt = a[x>>18 & 0777] + a[x>>9 & 0777] + a[x & 0777];
154
+ std::cout << cnt << std::endl; // 各値の合計
155
+
156
+ cnt = b[x>>18 & 0777] + b[x>>9 & 0777] + b[x & 0777];
157
+ std::cout << cnt << std::endl; // 各値が1以上の要素数
158
+
159
+ cnt = c[x>>18 & 0777] + c[x>>9 & 0777] + c[x & 0777];
160
+ std::cout << cnt << std::endl; // 各値が2以上の要素数
161
+
162
+ cnt = d[x>>18 & 0777] + d[x>>9 & 0777] + d[x & 0777];
163
+ std::cout << cnt << std::endl; // 各値が2の要素数
164
+ }
165
+ ```

7

コードの修正(変数 y の削除)

2020/09/16 01:52

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -35,7 +35,7 @@
35
35
  int main()
36
36
  {
37
37
  int x = 69510160;
38
- // (1)各値が2の要素数
38
+ // (1)各値が2の要素数
39
39
  {
40
40
  int cnt = 0;
41
41
  for (int i = 0; i < 27; i += 3) {
@@ -44,21 +44,20 @@
44
44
  }
45
45
  std::cout << cnt << std::endl;
46
46
  }
47
- // (2)各値が2の要素数
47
+ // (2)各値が2の要素数
48
- {
48
+ {
49
- int y = x ^ 0555555555;
49
+ int cnt = x ^ 0555555555;
50
- y &= y >> 2 & y >> 1;
50
+ cnt &= cnt >> 2 & cnt >> 1;
51
- int cnt = (y >> 3 & 01010101) + (y & 01010101);
51
+ cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24);
52
- cnt = (cnt >> 6 & 030003) + (cnt & 030003);
52
+ cnt = (cnt >> 6 & 030003) + (cnt & 030003);
53
- cnt = (cnt >> 12 & 7) + (cnt & 7);
53
+ cnt = (cnt >> 12 & 7) + (cnt & 7);
54
- cnt += y >> 24;
55
54
  std::cout << cnt << std::endl;
56
- }
55
+ }
57
56
  }
58
57
  ```
59
58
  演算回数
60
59
  (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、== 9回、++ 0～9回
61
- (2) = 4回、+= 1回、&= 1回、>> 6回、& 7回、+ 3回
60
+ (2) = 4回、^ 1回、+= 1回、&= 1回、>> 6回、& 7回、+ 4回
62
61
 
63
62
  **追記2**
64
63
  各値が1以上の要素数
@@ -79,18 +78,17 @@
79
78
  }
80
79
  // (2)各値が1以上の要素数
81
80
  {
82
- int y = x >> 2 | x >> 1 | x;
81
+ int cnt = x >> 2 | x >> 1 | x;
83
- int cnt = (y >> 3 & 01010101) + (y & 01010101);
82
+ cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24 & 1);
84
83
  cnt = (cnt >> 6 & 030003) + (cnt & 030003);
85
84
  cnt = (cnt >> 12 & 7) + (cnt & 7);
86
- cnt += y >> 24 & 1;
87
85
  std::cout << cnt << std::endl;
88
86
  }
89
87
  }
90
88
  ```
91
89
  演算回数
92
90
  (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
93
- (2) = 4回、+= 1回、| 2回、>> 6回、& 7回、+ 3回
91
+ (2) = 4回、| 2回、>> 6回、& 7回、+ 4回
94
92
 
95
93
  各値が2以上の要素数
96
94
  ```C++
@@ -110,14 +108,14 @@
110
108
  }
111
109
  // 各値が2以上の要素数
112
110
  {
113
- int y = x >> 2 | x >> 1;
111
+ int cnt = x >> 2 | x >> 1;
114
- int cnt = (y >> 3 & 01010101) + (y & 01010101);
112
+ cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24 & 1);
115
113
  cnt = (cnt >> 6 & 030003) + (cnt & 030003);
116
114
  cnt = (cnt >> 12 & 7) + (cnt & 7);
117
- cnt += y >> 24 & 1;
118
115
  std::cout << cnt << std::endl;
119
116
  }
120
117
  }
121
118
  ```
119
+ 演算回数
122
120
  (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
123
- (2) = 4回、+= 1回、| 1回、>> 6回、& 7回、+ 3回
121
+ (2) = 4回、| 1回、>> 6回、& 7回、+ 4回

6

1以上と 2以上のコードを追加

2020/09/15 19:09

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -57,5 +57,67 @@
57
57
  }
58
58
  ```
59
59
  演算回数
60
- (1) = 2回、< 9回、+= 9回、>> 9回、& 9回、== 9回、++ 0～9回
60
+ (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、== 9回、++ 0～9回
61
- (2) = 4回、+= 1回、&= 1回、>> 6回、& 7回、+ 3回
61
+ (2) = 4回、+= 1回、&= 1回、>> 6回、& 7回、+ 3回
62
+
63
+ **追記2**
64
+ 各値が1以上の要素数
65
+ ```C++
66
+ #include <iostream>
67
+
68
+ int main()
69
+ {
70
+ int x = 69510160;
71
+ // (1)各値が1以上の要素数
72
+ {
73
+ int cnt = 0;
74
+ for (int i = 0; i < 27; i += 3) {
75
+ if (x >> i & 0b111)
76
+ cnt++;
77
+ }
78
+ std::cout << cnt << std::endl;
79
+ }
80
+ // (2)各値が1以上の要素数
81
+ {
82
+ int y = x >> 2 | x >> 1 | x;
83
+ int cnt = (y >> 3 & 01010101) + (y & 01010101);
84
+ cnt = (cnt >> 6 & 030003) + (cnt & 030003);
85
+ cnt = (cnt >> 12 & 7) + (cnt & 7);
86
+ cnt += y >> 24 & 1;
87
+ std::cout << cnt << std::endl;
88
+ }
89
+ }
90
+ ```
91
+ 演算回数
92
+ (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
93
+ (2) = 4回、+= 1回、| 2回、>> 6回、& 7回、+ 3回
94
+
95
+ 各値が2以上の要素数
96
+ ```C++
97
+ #include <iostream>
98
+
99
+ int main()
100
+ {
101
+ int x = 69510160;
102
+ // 各値が2以上の要素数
103
+ {
104
+ int cnt = 0;
105
+ for (int i = 0; i < 27; i += 3) {
106
+ if (x >> i & 0b110)
107
+ cnt++;
108
+ }
109
+ std::cout << cnt << std::endl;
110
+ }
111
+ // 各値が2以上の要素数
112
+ {
113
+ int y = x >> 2 | x >> 1;
114
+ int cnt = (y >> 3 & 01010101) + (y & 01010101);
115
+ cnt = (cnt >> 6 & 030003) + (cnt & 030003);
116
+ cnt = (cnt >> 12 & 7) + (cnt & 7);
117
+ cnt += y >> 24 & 1;
118
+ std::cout << cnt << std::endl;
119
+ }
120
+ }
121
+ ```
122
+ (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
123
+ (2) = 4回、+= 1回、| 1回、>> 6回、& 7回、+ 3回

5

各値が2の要素数のコードを追加

2020/09/15 18:45

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -25,4 +25,37 @@
25
25
  ```
26
26
  演算回数
27
27
  (1) = 2回、< 10回、+= 18回、>> 9回、& 9回
28
- (2) = 3回、>> 4回、& 6回、+ 3回、+= 1回
28
+ (2) = 3回、>> 4回、& 6回、+ 3回、+= 1回
29
+
30
+ **追記**
31
+ 各値が2の要素数
32
+ ```C++
33
+ #include <iostream>
34
+
35
+ int main()
36
+ {
37
+ int x = 69510160;
38
+ // (1)各値が2の要素数
39
+ {
40
+ int cnt = 0;
41
+ for (int i = 0; i < 27; i += 3) {
42
+ if ((x >> i & 0b111) == 2)
43
+ cnt++;
44
+ }
45
+ std::cout << cnt << std::endl;
46
+ }
47
+ // (2)各値が2の要素数
48
+ {
49
+ int y = x ^ 0555555555;
50
+ y &= y >> 2 & y >> 1;
51
+ int cnt = (y >> 3 & 01010101) + (y & 01010101);
52
+ cnt = (cnt >> 6 & 030003) + (cnt & 030003);
53
+ cnt = (cnt >> 12 & 7) + (cnt & 7);
54
+ cnt += y >> 24;
55
+ std::cout << cnt << std::endl;
56
+ }
57
+ }
58
+ ```
59
+ 演算回数
60
+ (1) = 2回、< 9回、+= 9回、>> 9回、& 9回、== 9回、++ 0～9回
61
+ (2) = 4回、+= 1回、&= 1回、>> 6回、& 7回、+ 3回

4

余計なゼロの削除

2020/09/15 18:13

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -15,9 +15,9 @@
15
15
  }
16
16
  // (2)各値の合計
17
17
  {
18
- int cnt = (x >> 3 & 007070707) + (x & 007070707);
18
+ int cnt = (x >> 3 & 07070707) + (x & 07070707);
19
- cnt = (cnt >> 6 & 000170017) + (cnt & 000170017);
19
+ cnt = (cnt >> 6 & 0170017) + (cnt & 0170017);
20
- cnt = (cnt >> 12 & 000000037) + (cnt & 000000037);
20
+ cnt = (cnt >> 12 & 037) + (cnt & 037);
21
21
  cnt += x >> 24;
22
22
  std::cout << cnt << std::endl;
23
23
  }

3

77 -> 17、7777 -> 0037

2020/09/15 17:15

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -16,8 +16,8 @@
16
16
  // (2)各値の合計
17
17
  {
18
18
  int cnt = (x >> 3 & 007070707) + (x & 007070707);
19
- cnt = (cnt >> 6 & 000770077) + (cnt & 000770077);
19
+ cnt = (cnt >> 6 & 000170017) + (cnt & 000170017);
20
- cnt = (cnt >> 12 & 000007777) + (cnt & 000007777);
20
+ cnt = (cnt >> 12 & 000000037) + (cnt & 000000037);
21
21
  cnt += x >> 24;
22
22
  std::cout << cnt << std::endl;
23
23
  }

2

int cnt = に変更

2020/09/15 17:13

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -15,10 +15,9 @@
15
15
  }
16
16
  // (2)各値の合計
17
17
  {
18
- int cnt = x;
19
- cnt = (cnt >> 3 & 007070707) + (cnt & 007070707);
18
+ int cnt = (x >> 3 & 007070707) + (x & 007070707);
20
19
  cnt = (cnt >> 6 & 000770077) + (cnt & 000770077);
21
- cnt = (cnt >>12 & 000007777) + (cnt & 000007777);
20
+ cnt = (cnt >> 12 & 000007777) + (cnt & 000007777);
22
21
  cnt += x >> 24;
23
22
  std::cout << cnt << std::endl;
24
23
  }
@@ -26,4 +25,4 @@
26
25
  ```
27
26
  演算回数
28
27
  (1) = 2回、< 10回、+= 18回、>> 9回、& 9回
29
- (2) = 4回、>> 4回、& 6回、+ 3回、+= 1回
28
+ (2) = 3回、>> 4回、& 6回、+ 3回、+= 1回

1

< の回数訂正

2020/09/15 17:01

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -25,5 +25,5 @@
25
25
  }
26
26
  ```
27
27
  演算回数
28
- (1) = 2回、< 9回、+= 18回、>> 9回、& 9回
28
+ (1) = 2回、< 10回、+= 18回、>> 9回、& 9回
29
29
  (2) = 4回、>> 4回、& 6回、+ 3回、+= 1回