Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
    }
}
share|improve this question

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.