文章目錄

前言
- 求二進制中1的個數
1、第一種思路：n & 1
- 1.對1左移
- - 左移代碼
- 2.把n右移
- - 右移代碼
  - 右移缺陷
  - 2種改進代碼
2、第二種思路：n % 2
- 代碼
3、第三種思路：n & (n-1) (最容易想不到的)
- 代碼

前言

求二進制中1的個數

1、第一種思路：n & 1

對于任何一個數n和1按位與都會得到n的個位是不是1，其他位都會和0相與得0，
個位是0，運算式n&1的結果是0，個位是1，結果也是1.
在這里插入圖片描述
那么問題就來了這只能判斷個位呀，要是判斷其他位怎么整呀？？

不慌這里我們用移位運算子<<和>>

1.對1左移

每一次判斷一位之后把數字1左移一位
在這里插入圖片描述

左移代碼

int com_binary1(int n)//和1按位與  移動1
{
	int count = 0;
	int f = 1;
	while(f)
	{
		if(n & f)
			count++;
		f <<= 1;
		
	}
	return count;
}

2.把n右移

判斷完的位所對應的數可以丟棄直接右移
在這里插入圖片描述

右移代碼

int com_binary(int n)//和1按位與  移動n
{
	int count = 0;
	while (n)
	{
		count += n & 1;
		n >>= 1;
	}
	return count;
}

右移缺陷

大部分編譯器都是邏輯右移，那么很容易想到對于輸入一個負數每一次左移都會在最高位補1，那么最終就變成

0xFFFFFFFF

永遠大于0，從而陷入死回圈

2種改進代碼

一、對于32位平臺每個資料保存32位，可以控制移位次數來避免死回圈

int com_binary(int n)//和1按位與  移動n
{
	int count = 0;
	for (int i=0;i < 32;i++)
	{
		count += (n>>i) & 1;
	}
	return count;
}

二、改變傳進來的值型別為unsigned int
我們知道資料在計算機中存盤的是補碼，資料的正負主要看你讀取的形式，
因此我們可以把形參型別改為unsigned int 直接把傳進來的資料轉為無符號整形

int com_binary(unsigned int n)//和1按位與  移動n
{
	int count = 0;
	while (n)
	{
		count += n & 1;
		n >>= 1;
	}
	return count;
}

2、第二種思路：n % 2

在這里插入圖片描述
對于二進制來說從右往左每一位分別代表2的0次方，2的1次方…從第二位開始都是2的整數倍，只有第一位不是1就是0.所以n % 2正好是第一位的數字，
那么同理資料左移相當于把該數字 * 2，右移相當于 / 2.
在這里插入圖片描述
因此就可以每一次先 % 2，之后 / 2；

代碼

int com_binary3(unsigned int n)//模2除2
{
	int count = 0;
	while (n)
	{
		count += n % 2;
		n /= 2;
	}
	
	return count;
}

同理這種解法對于負數也會陷入死回圈中，需要把接收來的資料轉化為無符號

3、第三種思路：n & (n-1) (最容易想不到的)

在這里插入圖片描述

通過以上的例子可以看出n = n & n-1會把二進制中最右側的1變成0！！！！！！

代碼

int com_binary4(int n)//n&n-1
{
	int count = 0;
	while (n)
	{
		n= n & (n - 1);
		count++;
	}

	return count;
}

這種解法非常巧妙！！！