Leetcodeでeasyレベルの基礎的問題について解説して行きます。
基礎でもあるNumber of 1 Bitsというビットを計算する問題について記載しています。
※あくまで個人的な考え方ですので、より効率的な答えをお探しなら、Leetcodeの答えで人気なものを見るのもおすすめです。
Flutterをよく使用する私はDartを使って計算していますが、他の言語でもシンプルなため汎用性の高いものかなと思います。
ご参考になれば幸いです。
問題
Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).
Example 1:
Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.
Example 2:
Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.
Example 3:
Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.
日本語訳
「正の整数の2進数表現を受け取り、その中のセットビット（1であるビット）の数を返す関数を作成せよ（ハミング重みとも呼ばれる）。」
問題の意図
つまり、以下のようなイメージかなと思います。
- 10進数を2進数にする
- 2進数の中で「1」がいくつあるか計算してね
- それを関数として記載してね
解き方1 （ビット演算を使用）
この問題にはいろんな解き方がありますが、割とシンプルな下記の２つの解答について解説します。
- ビット演算を用いる方法
- 文字列を使用する方法
前提知識
2進数: 0001や0101のように0と1だけで表現される数字
10進数: 150や3000など日常で使っている数字
ビット演算: データを2進数で表して演算するもの
アンド演算(&): ビット演算の計算方法の一つで「1と1の場合のみ1とする」演算
例) 0001 と1010なら0000, 0001と1111なら0001となる
0001
1010
-----
0000
0001
1111
-----
0001
Dartの解答コード
int bitCount(int n) {
int count = 0;
while (n > 0) {
count += n & 1; // nの最下位ビットが1かどうかをチェック
n >>= 1; // nを1ビット右シフト
}
return count;
}
解説
やっていることとしては、以下のようなことをやっています。
- whileを使用してnが0になるまでループ
- And演算を用いてnの最下位ビットが1かチェックし「1」の場合にCountに1を足す
- nを1ビット右にシフトする
- ループが終わって計算したCountを返す
- whileを使用してCount変数を返している
while (n > 0) {
}
Whileを使用してnが0より大きい場合にループします。
- And演算を用いてnの最下位ビットが1かチェックし「1」の場合にCountに1を足す
count += n & 1;
Count + = は count = count + 1と一緒でカウントに1を足します。
N & 1はビット演算のアンド演算で10進数を2進数として計算します。
Nと0001をアンド演算して1ならcount変数が1プラスされます。
- nを1ビット右にシフトする
n >>= 1;
=を使用することで、ビットを右にシフトできてこの場合は1ビット右にシフトします。
これにより１ビットずつループして確認できます。
- ループが終わって計算したCountを返す
int bitCount(int n) {
int count = 0;
return count;
}
これはシンプルに最後にcount変数を返しているだけになります。
ビット演算を使用しての解き方について
ビット演算や2進数が苦手でなければすぐ解ける問題かなと思います。
やっていることもシンプルで簡単だと思います。
ビット演算子については、下記記事が参考になりました。
ビット演算については、下記2つの記事が参考になりました。
解き方2 （文字列を使用）
別の解き方として、文字列を使用する方法も紹介いたします。
Dartの解答コード
int bitCount2(int n) {
// toRadixString(2)で2進数文字列に変換
// split('')で1文字ずつのリストに変換
// where((bit) => bit == '1')で1の文字だけを抽出
return n.toRadixString(2).split('').where((bit) => bit == '1').length;
}
解説
こちらでは、文字列の中の「1」を探しています。
やっていることとしては、以下のようなことをやっています。
- toRadixString(2)で2進数文字列に変換
- split('')で1文字ずつのリストに変換
- where((bit) => bit == '1')で1の文字だけを抽出
- .lengthで数をカウント
1. toRadixString(2)で2進数文字列に変換
toRadixString()がDartにおける2進数文字列への変換になります。
2. split('')で1文字ずつのリストに変換
Splitを使って’’(空文字)で分割、つまり全てを数字を分割しています。
3.where((bit) => bit == '1')で1の文字だけを抽出
Whereを使用して’1’つまり1の文字列の場合を抽出しています。
4..lengthで数をカウント
最後にlengthでカウントしてnの中にいくつ1が入っている計算し終了です。
文字列を使用しての解き方について
こちらの方が1行でスッキリしていますが、下記のようなデメリットがあります。
簡潔で読みやすいが、文字列操作を行うため、メモリ使用量が増える可能性あり
ビット演算を直接使用するよりも効率が悪い
最後に
簡単な問題ですが、あまり競技プログラミングの世界に慣れていない私はよく忘れてしますのでここに記載しました。
どなたかのご参考になれば幸いです。