2022-03-10：限制：0 <= start <= end，0 <= target <= 64。
[start,end]范围上的数字，有多少数字二进制中1的个数等于target。
真实面试题，被问到了四五次，包括华为。
答案2022-03-10：
求0到x等于target的个数，然后做差。
代码用golang编写。代码如下：
```go
package main
import "fmt"
func main() {
ret := nums4(33281731, 204356810, 17)
fmt.Println(ret)
}
func nums4(start, end, target int) int {
if start < 0 || end < 0 || start > end || target < 0 {
return -1
}
anse := process4(63, target, end)
if start == 0 {
return anse
} else {
anss := process4(63, target, start-1)
return anse - anss
}
}
func process4(index, rest, num int) int {
if rest > index 1 {
return 0
}
if rest == 0 {
return 1
}
if (num & (1 << index)) == 0 {
return process4(index-1, rest, num)
} else {
return c(index, rest) process4(index-1, rest-1, num)
}
}
// 求C(N,A)的解
// N! / (A! * (N - A)!)
// 即 : (A 1 * A 2 * ... * N) / (2 * 3 * 4 * (N-A))
// 为了不溢出，每一步求一个最大公约数，然后消掉
func c(n, a int) int {
if n < a {
return 0
}
up := 1
down := 1
for i, j := a 1, 2; i <= n || j <= n-a; {
if i <= n {
up *= i
i
}
if j <= n-a {
down *= j
j
}
gcd := gcd0(up, down)
up /= gcd
down /= gcd
}
return up / down
}
// 求m和n的最大公约数
func gcd0(m, n int) int {
if n == 0 {
return m
} else {
return gcd0(n, m%n)
}
}
```
执行结果如下：
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2021_11_4_week/Code03_StartToEndBinaryOneTarget.java)
