1342.number-of-steps-to-reduce-a-number-to-zero.md

問題

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/

回答

初回の回答: 単純に条件分岐する

奇数なら-1、偶数なら/2 を実行してステップ数をカウントするという問題の条件を単純にコードに翻訳した実装。

impl Solution {
    pub fn number_of_steps(num: i32) -> i32 {
        let mut num = num;
        let mut count: i32 = 0;
        while num > 0 {
            if num % 2 == 0 {
                num /= 2;
            } else if num % 2 == 1 {
                num -= 1;
            } else if num == 0 {
                break;
            }
            count += 1;
        }
        count
    }
}

二回目の回答: ビット演算を使う

• 奇数なら-1
• 偶数なら/2

これの後者をビット演算に変換すると

• 奇数なら-1
• 偶数なら左に 1 論理シフト

になる。また、十進数を二進数に変換すると 0 と 1 だけになり、その数が奇数かどうかは最下位ビットが 1 かどうかで決まる。これは、

• 偶数 + 奇数 = 奇数
• 偶数 + 偶数 = 偶数

という偶奇性における法則によって判断できる。

桁	$2^2$	$2^1$	$2^0$
二進数	1	0	1

これを十進数に変換すると、

$$ 2^2 * 1 + 2^1 * 0 + 2^0 * 1 = 5 $$

となる。二進数の各桁は最下位ビット以外すべて偶数となるので、最下位ビットが $2^01$ か $2^00$ を見れば偶奇性がわかる。

たとえば 53 を 0 にするまでのステップ数を考えるとすると、二進数にすると 110101 なので、

1. 110101 奇数 -> -1
2. 110100 偶数 -> >>1
3. 11010  偶数 -> >>1
4. 1101   奇数 -> -1
5. 1100   偶数 -> >>1
6. 110    偶数 -> >>1
7. 11     奇数 -> -1
8. 1      奇数 -> -1
9. 0

合計 9 ステップ必要なことがわかる。奇数の場合は -1 と >>1 の両方が必要、偶数は >>1 だけで OK と考えると、

• 最下位ビットが 1 → 2 ステップ（※最後だけ-1 のみするので 1 ステップ引く）
• 最下位ビットが 0 → 1 ステップ

と考えることができる。あとは、0 と 1 の数がわかればそれぞれ計算して合計すれば OK 。 53 の場合、1 が 4 個、0 が 2 個、最後の 1 から 0 にするステップだけ >>1 が要らないので、

$$ 4 * 2 + 2 * 1 - 1 = 9 $$

となる。これをコードに落とし込めばいい。