2022-03-10：限制：0 ＜= start ＜= end，0 ＜= target ＜= 64。 [start,end]范围上的数字，有多少数字二进制中1的个数等于target。 真实面试题，被问

2022-03-10：限制：0 <= start <= end，0 <= target <= 64。
[start,end]范围上的数字，有多少数字二进制中1的个数等于target。
真实面试题，被问到了四五次，包括华为。

答案2022-03-10：

求0到x等于target的个数，然后做差。

代码用golang编写。代码如下：

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代码

2022-03-10：限制：0 ＜= start ＜= end，0 ＜= target ＜= 64。 [start,end]范围上的数字，有多少数字二进制中1的个数等于target。 真实面试题，被问的相关教程结束。