🐢

LeetCode - Complement of Base 10 Integer をSwiftで解説する

2020/10/25に公開

iOS

元の問題は英語なので、代わりに翻訳したものを記載しています。
回答はあくまでも例であり、他の方法も存在します。

前置き

Swiftでビット演算子を使ったことがない人にとっては、程よい問題かと思います。

問題

問題	難易度
1009. Complement of Base 10 Integer	easy

すべての非負の整数Nは2進表現を持っています。 
例えば、5は2進数で "101"、 11は2進数で "1011"などと表現することができます。 
N=0 を除いて、どんな2進表現でも先頭のゼロは存在しないことに注意してください。

2進表現の補数は、1 を 0 に、0 を 1 に変更したときに得られる 2進数です。 
例えば、2進表現の "101" の補数は 2進表現の "010" となります。

１０進数の与えられた数Nに対して、その2進表現の補数を１０進数の整数として返します。

つまり、以下の工程を行うことで結果を得ることができます。

与えられた１０進数を
① 2進数に変換 
② 補数の取得
③ 10進数に変換

答え

func bitwiseComplement(_ N: Int) -> Int {
    return String(N, radix: 2).map{ $0 == "1" ? 0 : 1 }.reduce(0){ $0 << 1 | $1 }
}

ワンライナーですっきりとした形で書くことができます。
ただし、これではわかりづらいと思うので、もう少し崩した形を用意しました。

func bitwiseComplement(_ N: Int) -> Int {
    // ① 2進数に変換 
    let str = String(N, radix: 2)
    
    var result = 0
    for i in str {
        // ② 補数の取得
	let k = (i == "1" ? 0 : 1)
	
	// ③ 数を合算
	let m = (result << 1)
        result = m | k
    }
    return result
}

このコードを元に解説を行っていきます。

解説

① 2進数に変換

Swiftには進数間を変換するためのAPIが予め用意されています。
答えの中では、この部分が該当します。

let str = String(N, radix: 2)

StringのAPIであることから察せられますが、同時にInt->Stringへの変換も行われます。実は、次の工程（補数の取得）を行う際に、数字を１つずつ取り出すのにStringだと都合が良かったりします。

補足

進数変換のAPI

String(/*対象の数*/, radix: /*進数*/)は、以下のような例で変換できます。

var n = 10
print(String(n, radix: 2))    // 1010
print(String(n, radix: 8))    // 12
print(String(n, radix: 10))   // 10
print(String(n, radix: 16))   // a

進数変換の実装

自前で10進数->2進数を行う処理を書く場合は、以下のように書けます。（１つの例として）

func convert(from n: Int) -> Int {
    var num = n, buf = 0, base = 1

    while 0 < num {
        buf += (num % 2) * base
        num /= 2
        base = base * 10
    }
    return buf
}

※ただし、この問題でこちらを使用すると、値が溢れてRuntime Errorになるので別の式が必要です

② 補数の取得

答えから実際に処理を行っている部分のコードだけを抜粋してきました。

for i in str {
    let k = (i == "1" ? 0 : 1)
    
    // 省略
}

Stringはfor文で回すことで１文字ずつ取得することができます。

それを利用してStringの2進数から数字を１つずつ取り出していき、その値が「"1"」かどうか判定し、１桁ずつ補数を求めていきます。

また、補数はStringではなくIntにすることで変換する手間を省いています。
（答えはIntで返す必要があるため。また次の工程で行う処理はIntだと都合が良いため。）

③ 数を合算

「② 補数の取得」で求めた１桁ずつの補数を、どこかに確保しておく必要があります。

var result = 0

そのためにresultという変数を用意しました。
では、求めた補数をresultに入れたコードにしてみます。

for i in str {
    let k = (i == "1" ? 0 : 1)
    result = k // 追加部分
}

このままでは毎回resultが更新されてしまうため、最後に求めた桁しか反映されません。

そのため、計算度に値を合算する必要があります。１桁ごとに計算を行いresultに反映していくので、桁の繰り上がりを意識する必要があります。そこで使うのがビット演算です。

具体的には、ビットシフトを行って前回の補数を繰り上げます。
そして、その補数と次の補数をビットORで合算していきます。

for i in str {
    let k = (i == "1" ? 0 : 1)
    
    // ビットシフトを行い１つ前の桁を繰り上げる
    let m = (result << 1)
    
    // 「上の桁の補数」と「現在の桁の補数」を合算する
    result = m | k
}

このようにしてresultには値の合算値が入り、無事に答えを導き出すことができます。

補足

ビットシフト: <<, >>

ある数の中の全てのビットを特定の桁数だけ移動する。

/* example */
let bits: UInt8 = 4   // 00000100
bits << 1             // 00001000
bits << 5             // 10000000
bits << 6             // 00000000
bits >> 2             // 00000001

ビットOR: |

それぞれの桁同士にOR演算を行う。

/* example */
let bitA: UInt8 = 0b11111100 // = 252
let bitB: UInt8 = 0b11110000 // = 240

bitA | bitB // 0b11111100 = 252

実行結果

Runtime	Memory
0~4ms	14MB前後