n二进制1的个数

leecode

题目描述

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

m 示例 1:

输入: n = 2 输出: [0,1,1] 解释: 0 --> 0 1 --> 1 2 --> 10 示例 2:

输入: n = 5 输出: [0,1,1,2,1,2] 解释: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/w3tCBm 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。\

解题思路

一个个数的方法太恶心了,就不用了

法1

最低0位,动态规划

1. 动态规划:f(n)=f(n-1)-fir0(n-1)+1 解释:第n个数的1的个数=(n-1)个数的1的个数-(n-1)首个0的位置(从0开始计数)+1
   eg:f(4)=f(3)[1的个数为2]-fir0(3)+1 3=(011)^2,从右往左第一个1是0号位,第二个1为1号位,第三个0为2号位
   所以fir0(3)=2
   所以f(4)=2-2+1=1
   4=(0100)一的个数为1
   根据此我们在用公式计算一下f(5)
   f(5)=f(4)-fir0(4)+1
   首个0在0号位,所以fir0(4)=0
   f(5)=1-0+1=2;;;;(5=(01001)1的个数为2) 这样就不用去一个个数1的个数了

for i, j := 0, 0; j < n; j++ { //i为上一个数的1的个数,j为当前的数字
  i = i - findfir0(j)
  a = append(a, i)//切片拼接 的函数
 }

找首个0的位置

// 找0的首位
func findfir0(n int) int {
i := -1 //记录0的位置减一,
for ; n&1 == 1; i++ {
 n >>= 1
}

法2

** Brian Kernighan 算法** 简单来讲就是通过循环n=n&(n-1)来判断1的个数,
eg:f(15) 1111(15)&1110(14)=1110(14)---(第一次)
1110(14)&1101(13)=1100(12)--(第二次)
1100(14)&1011(13)=1000(8)--(第3次)
1000(3)&111(7)=0---(第四次)
f(15)=4
其实就是一个个的数1的个数,但是会少很多无用的循环,就是每循环一次就会少一个1,比n=>>1&1好多了

for k := i; k > 0; j++ {//k为数值,j储存次数
   k &= k - 1
  }

执行结果

法1

func countBits(n int) []int {
 var a []int
 a = append(a, 0)
 for i, j := 0, 0; j < n; j++ { //i为上一个数的1的个数,j为当前的数字
  i = i - findfir0(j)
  a = append(a, i)
 }
 return a
}

// 找0的首位
func findfir0(n int) int {
 i := -1 //记录0的位置减一,
 for ; n&1 == 1; i++ {
  n >>= 1
 }
 return i
}

执行用时： 4 ms , 在所有 Go 提交中击败了 85.45% 的用户 内存消耗： 6 MB , 在所有 Go 提交中击败了 18.27% 的用户 通过测试用例： 15 / 15

优化空间

func countBits2(n int) []int {
 a := make([]int, n+1)//直接申请一个长度为n+1的数组就不用借用其他变量来储存了,也不用调用append函数了
 a[0] = 0
 for j := 0; j < n; j++ { //j为当前的数字
  a[j+1] = a[j] - findfir0(j)
 }
 return a
}

// 找0的首位
func findfir0(n int) int {
 i := -1 //记录0的位置减一,
 for ; n&1 == 1; i++ {
  n >>= 1
 }
 return i
}

执行用时： 4 ms , 在所有 Go 提交中击败了 85.45% 的用户 内存消耗： 4.3 MB , 在所有 Go 提交中击败了 99.69% 的用户 通过测试用例： 15 / 15

法2

func countBits3(n int) []int {
 a := make([]int, n+1)
 for i, j := 0, 0; i <= n; i++ { //i为索引,j储存次数,
  j = 0
  for k := i; k > 0; j++ {//k为数值,j储存次数
   k &= k - 1
  }
  a[i] = j
 }
 return a
}

执行用时： 4 ms , 在所有 Go 提交中击败了 85.45% 的用户 内存消耗： 4.3 MB , 在所有 Go 提交中击败了 84.52% 的用户 通过测试用例： 15 / 15