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

編集履歴

回答編集履歴

8

間違いがあるので非表示

2020/09/15 21:02

投稿

mjk
mjk

スコア303

answer CHANGED
@@ -1,155 +1,7 @@
1
- 実装はもっとスマートに出来ると思いますが考え方だけ。
1
+ ＃※間違いがあるので参考リンク以外を非表示にしておきます。
2
2
 
3
- ２以上の判定を行う例
4
- ２７桁のソースに対して必要なマスクとの論理演算を行います。
5
- `000000000000000100011010001`
6
- `010010010010010010010010010`
7
-
8
- 分解イメージ
9
- `000 000 000 000 000 100 011 010 001`
10
- `010 010 010 010 010 010 010 010 010`
11
- AND演算
12
- `000 000 000 000 000 000 010 010 000`
13
- 結果のONビットのものをbitsetのcountでカウントする。
14
-
15
- その他条件でも論理演算を数回組み合わせてマスクでふるいにかける感じで計算出来そうです。
16
- とりあえず>=1,==2,>=2は数えられました。
17
- 合計は全要素操作するしかないと思われるので割愛します。
18
-
19
3
  ---
20
-
21
4
  参考：[ビット演算](https://c.keicode.com/cpp/bitwise-operations.php)
22
5
 
23
6
 
24
- 参考：[ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜](https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361)
7
+ 参考：[ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜](https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361)
25
-
26
- ---
27
-
28
- 例==2かどうか
29
-
30
- 111 101 010 元データ
31
- 　　　　　　＆演算
32
- 010 010 010 チェックbit
33
- 　　　　　　
34
- 010 000 010 答え＝bit系関数でカウント
35
-
36
- AND演算後のONビットを数える関数で計算数回で出来そうです。
37
-
38
- ---
39
-
40
- こんな感じで出来ます。２７桁多いので９桁ですが。
41
- ```C++
42
- #include <bitset>
43
- #include <iostream>
44
-
45
- using namespace std;
46
-
47
- // >=2 )
48
- void f3() {
49
- string s1 = "100010001"; //ソース
50
- bitset<9> b1(s1);
51
- string s6 = "110110110"; //マスク６
52
- bitset<9> b6(s6);
53
- string s4 = "100100100"; //マスク４
54
- bitset<9> b4(s4);
55
- string s2 = "010010010"; //マスク２
56
- bitset<9> b2(s2);
57
-
58
- int sum = 0;
59
-
60
- cout << "b1 " << b1 << endl;
61
- cout << "b6 " << b6 << endl << endl;
62
- b1 = b1 & b6;
63
-
64
- bitset<9> b_tmp = b1;
65
-
66
- cout << "AND&) " << b1 << endl;
67
- cout << "b4 " << b4 << endl;
68
- cout << "b1 " << b1 << endl;
69
- b1 = b1 & b4;
70
- sum += b1.count();
71
- cout << "==4 ) " << b1.count() << endl << endl;
72
-
73
- cout << "AND&) " << b_tmp << endl;
74
- cout << "b2 " << b2 << endl;
75
- b1 = b_tmp & b2;
76
- cout << "b1 " << b1 << endl;
77
- sum += b1.count();
78
- cout << "2or3) " << b1.count() << endl << endl;
79
- cout << ">=2 ) " << sum << endl;
80
- }
81
-
82
- // ==2 )
83
- void f2() {
84
- string s1 = "100010001"; //ソース
85
- bitset<9> b1(s1);
86
- string s2 = "010010010"; //マスク
87
- bitset<9> b2(s2);
88
-
89
- cout << "b1 " << b1 << endl;
90
- cout << "b2 " << b2 << endl;
91
-
92
- b1 = b1 & b2;
93
- // b1 &= b2;
94
-
95
- cout << "AND&) " << b1 << endl;
96
-
97
- cout << "==2 ) " << b1.count() << endl << endl;
98
- }
99
-
100
- // >=1 )
101
- void f1() {
102
- string sc = "100010001"; //ソース
103
- bitset<9> bs(sc);
104
- string s4 = "100100100"; //マスク４
105
- bitset<9> b4(s4);
106
- string s2 = "010010010"; //マスク２
107
- bitset<9> b2(s2);
108
- string s1 = "001001001"; //マスク１
109
- bitset<9> b1(s1);
110
-
111
- int sum = 0;
112
- bitset<9> tp;
113
- tp = bs & b1;
114
- sum += tp.count();
115
- tp = bs & b2;
116
- sum += tp.count();
117
- tp = bs & b4;
118
- sum += tp.count();
119
- cout << ">=1 ) " << sum << endl << endl;
120
- }
121
-
122
- int main() {
123
- f1();
124
- f2();
125
- f3();
126
- getchar();
127
- }
128
-
129
- // 引用元
130
- // https://c.keicode.com/cpp/bitwise-operations.php
131
- ```
132
-
133
- ```output
134
- >=1 ) 3
135
-
136
- b1 100010001
137
- b2 010010010
138
- AND&) 000010000
139
- ==2 ) 1
140
-
141
- b1 100010001
142
- b6 110110110
143
-
144
- AND&) 100010000
145
- b4 100100100
146
- b1 100010000
147
- ==4 ) 1
148
-
149
- AND&) 100010000
150
- b2 010010010
151
- b1 000010000
152
- 2or3) 1
153
-
154
- >=2 ) 2
155
- ```

7

説明修正

2020/09/15 21:01

投稿

mjk
mjk

スコア303

answer CHANGED
@@ -1,7 +1,19 @@
1
1
  実装はもっとスマートに出来ると思いますが考え方だけ。
2
2
 
3
+ ２以上の判定を行う例
4
+ ２７桁のソースに対して必要なマスクとの論理演算を行います。
5
+ `000000000000000100011010001`
6
+ `010010010010010010010010010`
7
+
8
+ 分解イメージ
9
+ `000 000 000 000 000 100 011 010 001`
10
+ `010 010 010 010 010 010 010 010 010`
11
+ AND演算
12
+ `000 000 000 000 000 000 010 010 000`
13
+ 結果のONビットのものをbitsetのcountでカウントする。
14
+
3
- 論理演算を数回組み合わせてマスクでふるいにかける感じで計算出来るかも知れません。
15
+ その他条件でも論理演算を数回組み合わせてマスクでふるいにかける感じで計算出来そうです。
4
- とりあえず>=1,==2,>=2は数えられそうです。
16
+ とりあえず>=1,==2,>=2は数えられました。
5
17
  合計は全要素操作するしかないと思われるので割愛します。
6
18
 
7
19
  ---

6

出力修正

2020/09/15 18:33

投稿

mjk
mjk

スコア303

answer CHANGED
@@ -1,11 +1,31 @@
1
- こんな感じで出来ます。２７桁多いので９桁ですが。
1
+ 実装はもっとスマートに出来ると思いますが考え方だけ。
2
2
 
3
-
4
- 論理演算を数回組み合わせてマスクでふるいにかける感じで計算出来るかも知れませんね。
3
+ 論理演算を数回組み合わせてマスクでふるいにかける感じで計算出来るかも知れません。
5
4
  とりあえず>=1,==2,>=2は数えられそうです。
6
5
  合計は全要素操作するしかないと思われるので割愛します。
7
6
 
7
+ ---
8
8
 
9
+ 参考：[ビット演算](https://c.keicode.com/cpp/bitwise-operations.php)
10
+
11
+
12
+ 参考：[ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜](https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361)
13
+
14
+ ---
15
+
16
+ 例==2かどうか
17
+
18
+ 111 101 010 元データ
19
+ 　　　　　　＆演算
20
+ 010 010 010 チェックbit
21
+ 　　　　　　
22
+ 010 000 010 答え＝bit系関数でカウント
23
+
24
+ AND演算後のONビットを数える関数で計算数回で出来そうです。
25
+
26
+ ---
27
+
28
+ こんな感じで出来ます。２７桁多いので９桁ですが。
9
29
  ```C++
10
30
  #include <bitset>
11
31
  #include <iostream>
@@ -99,6 +119,8 @@
99
119
  ```
100
120
 
101
121
  ```output
122
+ >=1 ) 3
123
+
102
124
  b1 100010001
103
125
  b2 010010010
104
126
  AND&) 000010000
@@ -118,24 +140,4 @@
118
140
  2or3) 1
119
141
 
120
142
  >=2 ) 2
121
-
122
- ```
143
+ ```
123
-
124
- 参考：[ビット演算](https://c.keicode.com/cpp/bitwise-operations.php)
125
-
126
-
127
- 参考：[ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜](https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361)
128
-
129
- よく調べていませんが直感でいけそうかなと思ったので。
130
- 取り急ぎ思いつきですみません。
131
-
132
- 例==2かどうか
133
-
134
- 111 101 010 元データ
135
- 　　　　　　＆演算
136
- 010 010 010 チェックbit
137
- 　　　　　　
138
- 010 000 010 答え＝bit系関数でカウント
139
-
140
- AND演算後のONビットを数える関数で計算１回で出来そうですが
141
- 調べていないので関数を知りません。

5

>=1,>=2,==2 追記

2020/09/15 18:13

投稿

mjk
mjk

スコア303

answer CHANGED
@@ -2,9 +2,10 @@
2
2
 
3
3
 
4
4
  論理演算を数回組み合わせてマスクでふるいにかける感じで計算出来るかも知れませんね。
5
- とりあえず==2と　==4と　2or3は数えられそうです。
5
+ とりあえず>=1,==2,>=2は数えられそうです。
6
- >=1は書いてませんが同様に各ビット毎に1110 3回分count取れば数えられるはずです。
6
+ 合計は全要素操作するしかないと思われるので割愛します。
7
7
 
8
+
8
9
  ```C++
9
10
  #include <bitset>
10
11
  #include <iostream>
@@ -12,7 +13,7 @@
12
13
  using namespace std;
13
14
 
14
15
  // >=2 )
15
- void f2() {
16
+ void f3() {
16
17
  string s1 = "100010001"; //ソース
17
18
  bitset<9> b1(s1);
18
19
  string s6 = "110110110"; //マスク６
@@ -47,7 +48,7 @@
47
48
  }
48
49
 
49
50
  // ==2 )
50
- void f1() {
51
+ void f2() {
51
52
  string s1 = "100010001"; //ソース
52
53
  bitset<9> b1(s1);
53
54
  string s2 = "010010010"; //マスク
@@ -61,13 +62,35 @@
61
62
 
62
63
  cout << "AND&) " << b1 << endl;
63
64
 
64
- cout << "==2 ) " << b1.count() << endl;
65
+ cout << "==2 ) " << b1.count() << endl << endl;
65
66
  }
66
67
 
68
+ // >=1 )
69
+ void f1() {
70
+ string sc = "100010001"; //ソース
71
+ bitset<9> bs(sc);
72
+ string s4 = "100100100"; //マスク４
73
+ bitset<9> b4(s4);
74
+ string s2 = "010010010"; //マスク２
75
+ bitset<9> b2(s2);
76
+ string s1 = "001001001"; //マスク１
77
+ bitset<9> b1(s1);
78
+
79
+ int sum = 0;
80
+ bitset<9> tp;
81
+ tp = bs & b1;
82
+ sum += tp.count();
83
+ tp = bs & b2;
84
+ sum += tp.count();
85
+ tp = bs & b4;
86
+ sum += tp.count();
87
+ cout << ">=1 ) " << sum << endl << endl;
88
+ }
89
+
67
90
  int main() {
68
- // f1();
91
+ f1();
69
- cout << endl;
70
92
  f2();
93
+ f3();
71
94
  getchar();
72
95
  }
73
96
 

4

>=1の補足

2020/09/15 18:07

投稿

mjk
mjk

スコア303

answer CHANGED
@@ -3,6 +3,7 @@
3
3
 
4
4
  論理演算を数回組み合わせてマスクでふるいにかける感じで計算出来るかも知れませんね。
5
5
  とりあえず==2と　==4と　2or3は数えられそうです。
6
+ >=1は書いてませんが同様に各ビット毎に1110 3回分count取れば数えられるはずです。
6
7
 
7
8
  ```C++
8
9
  #include <bitset>

3

２以上の追記

2020/09/15 17:56

投稿

mjk
mjk

スコア303

answer CHANGED
@@ -1,32 +1,102 @@
1
1
  こんな感じで出来ます。２７桁多いので９桁ですが。
2
+
3
+
4
+ 論理演算を数回組み合わせてマスクでふるいにかける感じで計算出来るかも知れませんね。
5
+ とりあえず==2と　==4と　2or3は数えられそうです。
6
+
2
7
  ```C++
3
8
  #include <bitset>
4
9
  #include <iostream>
5
10
 
6
11
  using namespace std;
7
12
 
13
+ // >=2 )
8
- int main() {
14
+ void f2() {
9
- string s1 = "010010010";
15
+ string s1 = "100010001"; //ソース
10
16
  bitset<9> b1(s1);
11
- string s2 = "111101010";
17
+ string s6 = "110110110"; //マスク６
18
+ bitset<9> b6(s6);
19
+ string s4 = "100100100"; //マスク４
20
+ bitset<9> b4(s4);
21
+ string s2 = "010010010"; //マスク２
12
22
  bitset<9> b2(s2);
13
23
 
24
+ int sum = 0;
25
+
14
26
  cout << "b1 " << b1 << endl;
27
+ cout << "b6 " << b6 << endl << endl;
28
+ b1 = b1 & b6;
29
+
30
+ bitset<9> b_tmp = b1;
31
+
32
+ cout << "AND&) " << b1 << endl;
33
+ cout << "b4 " << b4 << endl;
34
+ cout << "b1 " << b1 << endl;
35
+ b1 = b1 & b4;
36
+ sum += b1.count();
37
+ cout << "==4 ) " << b1.count() << endl << endl;
38
+
39
+ cout << "AND&) " << b_tmp << endl;
15
40
  cout << "b2 " << b2 << endl;
41
+ b1 = b_tmp & b2;
42
+ cout << "b1 " << b1 << endl;
43
+ sum += b1.count();
44
+ cout << "2or3) " << b1.count() << endl << endl;
45
+ cout << ">=2 ) " << sum << endl;
46
+ }
16
47
 
48
+ // ==2 )
49
+ void f1() {
50
+ string s1 = "100010001"; //ソース
51
+ bitset<9> b1(s1);
52
+ string s2 = "010010010"; //マスク
53
+ bitset<9> b2(s2);
54
+
55
+ cout << "b1 " << b1 << endl;
56
+ cout << "b2 " << b2 << endl;
57
+
17
58
  b1 = b1 & b2;
18
59
  // b1 &= b2;
19
60
 
20
61
  cout << "AND&) " << b1 << endl;
21
62
 
22
63
  cout << "==2 ) " << b1.count() << endl;
64
+ }
23
65
 
66
+ int main() {
67
+ // f1();
68
+ cout << endl;
69
+ f2();
24
70
  getchar();
25
71
  }
26
72
 
73
+ // 引用元
27
74
  // https://c.keicode.com/cpp/bitwise-operations.php
28
75
  ```
29
76
 
77
+ ```output
78
+ b1 100010001
79
+ b2 010010010
80
+ AND&) 000010000
81
+ ==2 ) 1
82
+
83
+ b1 100010001
84
+ b6 110110110
85
+
86
+ AND&) 100010000
87
+ b4 100100100
88
+ b1 100010000
89
+ ==4 ) 1
90
+
91
+ AND&) 100010000
92
+ b2 010010010
93
+ b1 000010000
94
+ 2or3) 1
95
+
96
+ >=2 ) 2
97
+
98
+ ```
99
+
30
100
  参考：[ビット演算](https://c.keicode.com/cpp/bitwise-operations.php)
31
101
 
32
102
 

2

コード追記

2020/09/15 17:40

投稿

mjk
mjk

スコア303

answer CHANGED
@@ -1,3 +1,35 @@
1
+ こんな感じで出来ます。２７桁多いので９桁ですが。
2
+ ```C++
3
+ #include <bitset>
4
+ #include <iostream>
5
+
6
+ using namespace std;
7
+
8
+ int main() {
9
+ string s1 = "010010010";
10
+ bitset<9> b1(s1);
11
+ string s2 = "111101010";
12
+ bitset<9> b2(s2);
13
+
14
+ cout << "b1 " << b1 << endl;
15
+ cout << "b2 " << b2 << endl;
16
+
17
+ b1 = b1 & b2;
18
+ // b1 &= b2;
19
+
20
+ cout << "AND&) " << b1 << endl;
21
+
22
+ cout << "==2 ) " << b1.count() << endl;
23
+
24
+ getchar();
25
+ }
26
+
27
+ // https://c.keicode.com/cpp/bitwise-operations.php
28
+ ```
29
+
30
+ 参考：[ビット演算](https://c.keicode.com/cpp/bitwise-operations.php)
31
+
32
+
1
33
  参考：[ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜](https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361)
2
34
 
3
35
  よく調べていませんが直感でいけそうかなと思ったので。

1

リンク追加

2020/09/15 16:18

投稿

mjk
mjk

スコア303

answer CHANGED
@@ -1,3 +1,5 @@
1
+ 参考：[ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜](https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361)
2
+
1
3
  よく調べていませんが直感でいけそうかなと思ったので。
2
4
  取り急ぎ思いつきですみません。
3
5