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

編集履歴

回答編集履歴

8

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

2020/09/16 01:52

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -239,3 +239,91 @@
239
239
  (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
240
240
 
241
241
  (2) = 4回、| 1回、>> 6回、& 7回、+ 4回
242
+
243
+
244
+
245
+ **追記3**
246
+
247
+ 表検索のため演算回数が少ない高速版
248
+
249
+ ```C++
250
+
251
+ #include <iostream>
252
+
253
+
254
+
255
+ #define A3(x) x,x+1,x+2,x+3,x+4,x+5,x+6,x+7
256
+
257
+ #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)
258
+
259
+ #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)
260
+
261
+ char a[512] = { A9(0) };
262
+
263
+
264
+
265
+ #define B3(x) x,x+1,x+1,x+1,x+1,x+1,x+1,x+1
266
+
267
+ #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)
268
+
269
+ #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)
270
+
271
+ char b[512] = { B9(0) };
272
+
273
+
274
+
275
+ #define C3(x) x,x,x+1,x+1,x+1,x+1,x+1,x+1
276
+
277
+ #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)
278
+
279
+ #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)
280
+
281
+ char c[512] = { C9(0) };
282
+
283
+
284
+
285
+ #define D3(x) x,x,x+1,x,x,x,x,x
286
+
287
+ #define D6(x) D3(x),D3(x),D3(x+1),D3(x),D3(x),D3(x),D3(x),D3(x)
288
+
289
+ #define D9(x) D6(x),D6(x),D6(x+1),D6(x),D6(x),D6(x),D6(x),D6(x)
290
+
291
+ char d[512] = { D9(0) };
292
+
293
+
294
+
295
+ int main()
296
+
297
+ {
298
+
299
+ int x = 69510160;
300
+
301
+ int cnt;
302
+
303
+
304
+
305
+ cnt = a[x>>18 & 0777] + a[x>>9 & 0777] + a[x & 0777];
306
+
307
+ std::cout << cnt << std::endl; // 各値の合計
308
+
309
+
310
+
311
+ cnt = b[x>>18 & 0777] + b[x>>9 & 0777] + b[x & 0777];
312
+
313
+ std::cout << cnt << std::endl; // 各値が1以上の要素数
314
+
315
+
316
+
317
+ cnt = c[x>>18 & 0777] + c[x>>9 & 0777] + c[x & 0777];
318
+
319
+ std::cout << cnt << std::endl; // 各値が2以上の要素数
320
+
321
+
322
+
323
+ cnt = d[x>>18 & 0777] + d[x>>9 & 0777] + d[x & 0777];
324
+
325
+ std::cout << cnt << std::endl; // 各値が2の要素数
326
+
327
+ }
328
+
329
+ ```

7

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

2020/09/16 01:52

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -72,7 +72,7 @@
72
72
 
73
73
  int x = 69510160;
74
74
 
75
- // (1)各値が2の要素数
75
+ // (1)各値が2の要素数
76
76
 
77
77
  {
78
78
 
@@ -90,22 +90,82 @@
90
90
 
91
91
  }
92
92
 
93
- // (2)各値が2の要素数
93
+ // (2)各値が2の要素数
94
-
94
+
95
- {
95
+ {
96
-
96
+
97
- int y = x ^ 0555555555;
97
+ int cnt = x ^ 0555555555;
98
-
98
+
99
- y &= y >> 2 & y >> 1;
99
+ cnt &= cnt >> 2 & cnt >> 1;
100
+
100
-
101
+ cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24);
102
+
101
- int cnt = (y >> 3 & 01010101) + (y & 01010101);
103
+ cnt = (cnt >> 6 & 030003) + (cnt & 030003);
104
+
105
+ cnt = (cnt >> 12 & 7) + (cnt & 7);
106
+
107
+ std::cout << cnt << std::endl;
108
+
109
+ }
110
+
111
+ }
112
+
113
+ ```
114
+
115
+ 演算回数
116
+
117
+ (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、== 9回、++ 0～9回
118
+
119
+ (2) = 4回、^ 1回、+= 1回、&= 1回、>> 6回、& 7回、+ 4回
120
+
121
+
122
+
123
+ **追記2**
124
+
125
+ 各値が1以上の要素数
126
+
127
+ ```C++
128
+
129
+ #include <iostream>
130
+
131
+
132
+
133
+ int main()
134
+
135
+ {
136
+
137
+ int x = 69510160;
138
+
139
+ // (1)各値が1以上の要素数
140
+
141
+ {
142
+
143
+ int cnt = 0;
144
+
145
+ for (int i = 0; i < 27; i += 3) {
146
+
147
+ if (x >> i & 0b111)
148
+
149
+ cnt++;
150
+
151
+ }
152
+
153
+ std::cout << cnt << std::endl;
154
+
155
+ }
156
+
157
+ // (2)各値が1以上の要素数
158
+
159
+ {
160
+
161
+ int cnt = x >> 2 | x >> 1 | x;
162
+
163
+ cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24 & 1);
102
164
 
103
165
  cnt = (cnt >> 6 & 030003) + (cnt & 030003);
104
166
 
105
167
  cnt = (cnt >> 12 & 7) + (cnt & 7);
106
168
 
107
- cnt += y >> 24;
108
-
109
169
  std::cout << cnt << std::endl;
110
170
 
111
171
  }
@@ -116,29 +176,27 @@
116
176
 
117
177
  演算回数
118
178
 
119
- (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、== 9回、++ 0～9回
179
+ (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
120
-
180
+
121
- (2) = 4回、+= 1回、&= 1回、>> 6回、& 7回、+ 3回
181
+ (2) = 4回、| 2回、>> 6回、& 7回、+ 4回
122
-
123
-
124
-
125
- **追記2**
182
+
126
-
183
+
184
+
127
- 各値が1以上の要素数
185
+ 各値が2以上の要素数
128
-
186
+
129
- ```C++
187
+ ```C++
130
-
188
+
131
- #include <iostream>
189
+ #include <iostream>
132
-
133
-
134
-
190
+
191
+
192
+
135
- int main()
193
+ int main()
136
-
194
+
137
- {
195
+ {
138
-
196
+
139
- int x = 69510160;
197
+ int x = 69510160;
140
-
198
+
141
- // (1)各値が1以上の要素数
199
+ // 各値が2以上の要素数
142
200
 
143
201
  {
144
202
 
@@ -146,7 +204,7 @@
146
204
 
147
205
  for (int i = 0; i < 27; i += 3) {
148
206
 
149
- if (x >> i & 0b111)
207
+ if (x >> i & 0b110)
150
208
 
151
209
  cnt++;
152
210
 
@@ -156,20 +214,18 @@
156
214
 
157
215
  }
158
216
 
159
- // (2)各値が1以上の要素数
217
+ // 各値が2以上の要素数
160
-
218
+
161
- {
219
+ {
162
-
220
+
163
- int y = x >> 2 | x >> 1 | x;
221
+ int cnt = x >> 2 | x >> 1;
164
-
222
+
165
- int cnt = (y >> 3 & 01010101) + (y & 01010101);
223
+ cnt = (cnt >> 3 & 01010101) + (cnt & 01010101) + (cnt >> 24 & 1);
166
224
 
167
225
  cnt = (cnt >> 6 & 030003) + (cnt & 030003);
168
226
 
169
227
  cnt = (cnt >> 12 & 7) + (cnt & 7);
170
228
 
171
- cnt += y >> 24 & 1;
172
-
173
229
  std::cout << cnt << std::endl;
174
230
 
175
231
  }
@@ -182,64 +238,4 @@
182
238
 
183
239
  (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
184
240
 
185
- (2) = 4回、+= 1回、| 2回、>> 6回、& 7回、+ 3回
186
-
187
-
188
-
189
- 各値が2以上の要素数
190
-
191
- ```C++
192
-
193
- #include <iostream>
194
-
195
-
196
-
197
- int main()
198
-
199
- {
200
-
201
- int x = 69510160;
202
-
203
- // 各値が2以上の要素数
204
-
205
- {
206
-
207
- int cnt = 0;
208
-
209
- for (int i = 0; i < 27; i += 3) {
210
-
211
- if (x >> i & 0b110)
212
-
213
- cnt++;
214
-
215
- }
216
-
217
- std::cout << cnt << std::endl;
218
-
219
- }
220
-
221
- // 各値が2以上の要素数
222
-
223
- {
224
-
225
- int y = x >> 2 | x >> 1;
226
-
227
- int cnt = (y >> 3 & 01010101) + (y & 01010101);
228
-
229
- cnt = (cnt >> 6 & 030003) + (cnt & 030003);
230
-
231
- cnt = (cnt >> 12 & 7) + (cnt & 7);
232
-
233
- cnt += y >> 24 & 1;
234
-
235
- std::cout << cnt << std::endl;
236
-
237
- }
238
-
239
- }
240
-
241
- ```
242
-
243
- (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
244
-
245
- (2) = 4回、+= 1回、| 1回、>> 6回、& 7回、+ 3回
241
+ (2) = 4回、| 1回、>> 6回、& 7回、+ 4回

6

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

2020/09/15 19:09

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -116,6 +116,130 @@
116
116
 
117
117
  演算回数
118
118
 
119
- (1) = 2回、< 9回、+= 9回、>> 9回、& 9回、== 9回、++ 0～9回
119
+ (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、== 9回、++ 0～9回
120
120
 
121
121
  (2) = 4回、+= 1回、&= 1回、>> 6回、& 7回、+ 3回
122
+
123
+
124
+
125
+ **追記2**
126
+
127
+ 各値が1以上の要素数
128
+
129
+ ```C++
130
+
131
+ #include <iostream>
132
+
133
+
134
+
135
+ int main()
136
+
137
+ {
138
+
139
+ int x = 69510160;
140
+
141
+ // (1)各値が1以上の要素数
142
+
143
+ {
144
+
145
+ int cnt = 0;
146
+
147
+ for (int i = 0; i < 27; i += 3) {
148
+
149
+ if (x >> i & 0b111)
150
+
151
+ cnt++;
152
+
153
+ }
154
+
155
+ std::cout << cnt << std::endl;
156
+
157
+ }
158
+
159
+ // (2)各値が1以上の要素数
160
+
161
+ {
162
+
163
+ int y = x >> 2 | x >> 1 | x;
164
+
165
+ int cnt = (y >> 3 & 01010101) + (y & 01010101);
166
+
167
+ cnt = (cnt >> 6 & 030003) + (cnt & 030003);
168
+
169
+ cnt = (cnt >> 12 & 7) + (cnt & 7);
170
+
171
+ cnt += y >> 24 & 1;
172
+
173
+ std::cout << cnt << std::endl;
174
+
175
+ }
176
+
177
+ }
178
+
179
+ ```
180
+
181
+ 演算回数
182
+
183
+ (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
184
+
185
+ (2) = 4回、+= 1回、| 2回、>> 6回、& 7回、+ 3回
186
+
187
+
188
+
189
+ 各値が2以上の要素数
190
+
191
+ ```C++
192
+
193
+ #include <iostream>
194
+
195
+
196
+
197
+ int main()
198
+
199
+ {
200
+
201
+ int x = 69510160;
202
+
203
+ // 各値が2以上の要素数
204
+
205
+ {
206
+
207
+ int cnt = 0;
208
+
209
+ for (int i = 0; i < 27; i += 3) {
210
+
211
+ if (x >> i & 0b110)
212
+
213
+ cnt++;
214
+
215
+ }
216
+
217
+ std::cout << cnt << std::endl;
218
+
219
+ }
220
+
221
+ // 各値が2以上の要素数
222
+
223
+ {
224
+
225
+ int y = x >> 2 | x >> 1;
226
+
227
+ int cnt = (y >> 3 & 01010101) + (y & 01010101);
228
+
229
+ cnt = (cnt >> 6 & 030003) + (cnt & 030003);
230
+
231
+ cnt = (cnt >> 12 & 7) + (cnt & 7);
232
+
233
+ cnt += y >> 24 & 1;
234
+
235
+ std::cout << cnt << std::endl;
236
+
237
+ }
238
+
239
+ }
240
+
241
+ ```
242
+
243
+ (1) = 2回、< 10回、+= 9回、>> 9回、& 9回、!=0 9回、++ 0～9回
244
+
245
+ (2) = 4回、+= 1回、| 1回、>> 6回、& 7回、+ 3回

5

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

2020/09/15 18:45

投稿

kazuma-s
kazuma-s

スコア8224

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

4

余計なゼロの削除

2020/09/15 18:13

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -32,11 +32,11 @@
32
32
 
33
33
  {
34
34
 
35
- int cnt = (x >> 3 & 007070707) + (x & 007070707);
35
+ int cnt = (x >> 3 & 07070707) + (x & 07070707);
36
36
 
37
- cnt = (cnt >> 6 & 000170017) + (cnt & 000170017);
37
+ cnt = (cnt >> 6 & 0170017) + (cnt & 0170017);
38
38
 
39
- cnt = (cnt >> 12 & 000000037) + (cnt & 000000037);
39
+ cnt = (cnt >> 12 & 037) + (cnt & 037);
40
40
 
41
41
  cnt += x >> 24;
42
42
 

3

77 -> 17、7777 -> 0037

2020/09/15 17:15

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -34,9 +34,9 @@
34
34
 
35
35
  int cnt = (x >> 3 & 007070707) + (x & 007070707);
36
36
 
37
- cnt = (cnt >> 6 & 000770077) + (cnt & 000770077);
37
+ cnt = (cnt >> 6 & 000170017) + (cnt & 000170017);
38
38
 
39
- cnt = (cnt >> 12 & 000007777) + (cnt & 000007777);
39
+ cnt = (cnt >> 12 & 000000037) + (cnt & 000000037);
40
40
 
41
41
  cnt += x >> 24;
42
42
 

2

int cnt = に変更

2020/09/15 17:13

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -32,13 +32,11 @@
32
32
 
33
33
  {
34
34
 
35
- int cnt = x;
36
-
37
- cnt = (cnt >> 3 & 007070707) + (cnt & 007070707);
35
+ int cnt = (x >> 3 & 007070707) + (x & 007070707);
38
36
 
39
37
  cnt = (cnt >> 6 & 000770077) + (cnt & 000770077);
40
38
 
41
- cnt = (cnt >>12 & 000007777) + (cnt & 000007777);
39
+ cnt = (cnt >> 12 & 000007777) + (cnt & 000007777);
42
40
 
43
41
  cnt += x >> 24;
44
42
 
@@ -54,4 +52,4 @@
54
52
 
55
53
  (1) = 2回、< 10回、+= 18回、>> 9回、& 9回
56
54
 
57
- (2) = 4回、>> 4回、& 6回、+ 3回、+= 1回
55
+ (2) = 3回、>> 4回、& 6回、+ 3回、+= 1回

1

< の回数訂正

2020/09/15 17:01

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -52,6 +52,6 @@
52
52
 
53
53
  演算回数
54
54
 
55
- (1) = 2回、< 9回、+= 18回、>> 9回、& 9回
55
+ (1) = 2回、< 10回、+= 18回、>> 9回、& 9回
56
56
 
57
57
  (2) = 4回、>> 4回、& 6回、+ 3回、+= 1回