LeetCode Counting Bits in Swift

Question

I solve this problem in Swift. I am looking for a code review, thanks!

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

class Solution {
    func countBits(num: Int) -> [Int] {
        var nums = [Int](count: num+1, repeatedValue: 0)
        if num == 0 { // if num is 0
            return nums
        }
        for i in 1...num {
            nums[i] = binaryOnes(i)
        }
        return nums
    }
    func binaryOnes(num: Int) -> Int {
        var num = num
        var count = 0
        repeat  {
            if num % 2 == 0 { // even numbers
                num /= 2
            } else { // all odd numbers
                num = (num-1)/2
                count += 1
            }
        } while num > 1
        if num == 1 { // when num is 1 at the end
            count += 1
        }
        return count
    }
}

Answer 1

Both methods don't use any state of the Solution class, so they should be static methods of that type, or global functions.

binaryOnes() can be simplified. If you replace

repeat { ... } while num > 1

by

while num > 0 { ... }

then the additional check for num == 1 becomes obsolete:

func binaryOnes(num: Int) -> Int {
    var num = num
    var count = 0
    while num > 0 {
        if num % 2 == 0 { // even numbers
            num /= 2
        } else { // all odd numbers
            num = (num-1)/2
            count += 1
        }
    }
    return count
}

Now observe that num % 2 gives the least significant bit of the number (0 or 1), and num /= 2 is a truncating division. Therefore the function can be simplified to

func binaryOnes(num: Int) -> Int {
    var num = num
    var count = 0
    while num > 0 {
        count += num % 2
        num /= 2
    }
    return count
}

More sophisticated bit counting methods can be found at https://graphics.stanford.edu/~seander/bithacks.html, they can be more effective for large numbers.

In countBits, the check for num == 0 is not necessary, because 1...num is the empty range in that case:

func countBits(num: Int) -> [Int] {
    var nums = [Int](count: num+1, repeatedValue: 0)
    for i in 1...num {
        nums[i] = binaryOnes(i)
    }
    return nums
}

Calling the variables num and nums could be confusing, upTo: might be a better name for the parameter.

But what the function actually does is to map the numbers 0...upTo to their bit count. That can be done directly with a map() method:

func countBits(upTo: Int) -> [Int] {
    return (0...upTo).map(binaryOnes)
}

An alternative approach would be to use the fact that

bitCount(n) = bitCount(n/2) + (n % 2)

for all (positive) integers n. Together with bitCount(0) = 0 this is a recursive computation method. But since you store the bit counts in an array anyway, this can be implemented as a simple iteration:

func countBits1(upTo: Int) -> [Int] {
    var result = [ 0 ]
    for i in 1...upTo {
        result.append(result[i/2] + (i % 2))
    }
    return result
}

Now the binaryOnes() function is not needed anymore.

Answer 2

// ********* 338. Counting Bits *********

The previous solution will fail for the input [0].

func countBits(_ num: Int) -> [Int] {
    var result = [0]
    guard num != 0 else {
        return result
    }
    for i in 1...num {
        result.append(result[i/2] + (i % 2))
    }
    return result
}