如何利用C語言位運算解決只出現(xiàn)一次的數(shù)字

更新時間：2021年04月07日 12:05:50 作者：預選碼農001

這篇文章主要給大家介紹了關于如何利用C語言位運算解決只出現(xiàn)一次的數(shù)字的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

解題所需要的C語言基礎知識

hello！從現(xiàn)在開始就進入本題解的正式內容了。首先給大家用圖解的方式介紹3個C語言位運算的基本操作符 & | ^

這些知識對下面的解題都非常重要，一定要熟練掌握，不然等會會有一種“我在哪，我是誰我在干什么”的感覺。

只出現(xiàn)一次的數(shù)字I

題目描述

只出現(xiàn)一次的數(shù)字
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。
說明：

你的算法應該具有線性時間復雜度。你可以不使用額外空間來實現(xiàn)嗎？

示例 1:

輸入: [2,2,1] 輸出: 1
示例 2:

輸入: [4,1,2,1,2] 輸出: 4

力扣本題鏈接

解題思路

首先，根據(jù)題意，“有不可以額外使用空間這個限定”，看到這里以后要本能的往位運算上面去靠，因為位運算可以不開辟額外空間解決很多問題，然后回看一下剛剛回顧的位運算知識，就知道我們要用到 ^這個操作符了，因為它可以非常簡單的消除重復項，剩下只出現(xiàn)一次的數(shù)字。

說了這么多，接下來讓我們來看看代碼的實現(xiàn)

int singleNumber(int* nums, int numsSize){
int ret=0;//0異或任何數(shù)都不會印象他的實際值
for(int i=0;i<numsSize;i++)
{
 ret^=nums[i];//所有數(shù)異或，重復的消掉，剩下只出現(xiàn)一次的數(shù)字
}
return ret;//返回這個數(shù)字
}

這只是一個開胃菜，下面正式進入主菜

只出現(xiàn)一次的數(shù)字II

題目描述

只出現(xiàn)一次的數(shù)字 II 給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)了三次。找出那個只出現(xiàn)了一次的元素。
說明：

你的算法應該具有線性時間復雜度。你可以不使用額外空間來實現(xiàn)嗎？

示例 1:

輸入: [2,2,3,2] 輸出: 3
``示例 2:

輸入: [0,1,0,1,0,1,99] 輸出: 99

力扣本題鏈接

解題思路

如圖所示，考慮數(shù)字的二進制位形式，出現(xiàn)三次的數(shù)字，二進制位各位上的1都是三的倍數(shù)，所以求出各位上的1數(shù)目，再對3求余，則可求出只出現(xiàn)一次的數(shù)字

那么要怎樣求取二進制位各位上1的數(shù)目吶，那就要用到&這個操作符了，來看代碼實現(xiàn)吧

int singleNumber(int* nums, int numsSize){
 
 int ret=0;
for(int i=0;i<32;++i)//循環(huán)遍歷二進制位每一位
{
long cnt=0;//不用long，力扣的編譯器不通過，不讓int類型左移31位，我也不知道
 for(int j=0;j<numsSize;++j) {//將nums數(shù)組中每一個數(shù)拿出來，二進制位向右移動i位，與1按位與，
 cnt+=(nums[j]>>i)&1;//則可求出二進制位第i位是否為1；
 }
 ret+=(cnt%3)<<i;//將cnt的值模3，求出只出現(xiàn)一次的那個數(shù)第i位為1還是為0，再向左移動i位還原，最后相加求出這個數(shù)
}
return ret;
}

好了，這個題目就圓滿解決了。

只出現(xiàn)一次的數(shù)字III

這個題目就很有技巧了題目描述
260. 只出現(xiàn)一次的數(shù)字 III 給定一個整數(shù)數(shù)組 nums，其中恰好有兩個元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。找出只出現(xiàn)一次的那兩個元素。你可以按任意順序返回答案。

進階：你的算法應該具有線性時間復雜度。你能否僅使用常數(shù)空間復雜度來實現(xiàn)？

示例 1：

輸入：nums = [1,2,1,3,2,5] 輸出：[3,5] 解釋：[5, 3] 也是有效的答案。
示例 2：

輸入：nums = [-1,0] 輸出：[-1,0]
示例 3：

輸入：nums = [0,1] 輸出：[1,0]

力扣本題鏈接

解題思路

根據(jù)第一題的思路，就知道要全部按位異或，消除重復項。但是兩個只出現(xiàn)一次的數(shù)也異或在了一起，我們的難點就是怎么將這兩個數(shù)分離。接下來就用圖示法來告訴大家怎樣分離兩個數(shù)

接下來是代碼的實現(xiàn)

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
int m = 0;
int ret = 0;
for (int i = 0; i < numsSize; i++)
{
	ret ^= nums[i];//將全部數(shù)異或
}
while (m < 32)
{
	if ((ret>>m)&1)//找出為1的第m位
		break;
	else
  ++m;
}
int x1 = 0, x2 = 0;//分組
int j=0;
while(j<numsSize)
{
	if ((nums[j]>>m)&1)
		x1 ^= nums[j];//異或出只出現(xiàn)一次的數(shù)字
	else
		x2 ^= nums[j];
  j++;
}
int* reRer = (int*)malloc(sizeof(int) * 2);
reRer[0] = x1;
reRer[1] = x2;
*returnSize=2;//根據(jù)題意返回長度
return reRer;//返回這兩個數(shù)
}