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
 }
}

• Marcy: Just putting the Swift built-in solution should anyone be looking for it here.(0...n).map{0ドル.nonzeroBitCount}

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
}

• Toby Speight: You have presented an alternative solution, but haven't reviewed the code. Please edit to show what aspects of the question code prompted you to write this version, and in what ways it's an improvement over the original. It may be worth (re-)reading How to Answer.
• user550088: @TobySpeight Thanks for the constructive criticism. Yup I wrote it like stack-overflow and not like code-review. Will take your suggestion for my future responses.