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.