刷题：位运算

怼烎@ 2021-12-19 23:05 264阅读 0赞

# 有关位运算的几个经典题目 #

#include<iostream>
    
    using namespace std;
    
    // 不使用中间变量交换两个整数的值
    void swap(int &a, int &b)
    {
    	a  = a ^ b;
    	b  = a ^ b;
    	a  = a ^ b;
    }
    
    // 整数的二进制表达中有多少个1
    int number_of_one(int n)
    {
    	int result = 0;
    	while (n != 0)
    	{
    		n = n & (n - 1);
    		result++;
    	}
    	return result;
    }
    //在一个整数数组中，只有1个数出现了奇数次，其余数都出现了偶数次，找出出现奇数次的数。
    int FindOddtimesNum(int arr[],int n)
    {
    	int result = 0;
    	for (int i = 0; i < n; ++i)
    	{
    		result ^= arr[i];
    	}
    
    	return result;
    }
    
    //在一个整数数组中，只有2个数出现了奇数次，其余数都出现了偶数次，找出出现奇数次的数。
    void FindOddtimesNum_2(int arr[], int n)
    {
    	int num_1 = 0, num_2 = 0;
    	for (int i = 0; i < n; ++i)
    	{
    		num_1 ^= arr[i];
    	}
    	int rightone = num_1 & (~num_1 +1 );
    
    	for (int i = 0; i < n; ++i)
    	{
    		if ((arr[i] & rightone) != 0) //与运算一定要加括号，要不然会出错
    			num_2 ^= arr[i];
    	}
    
    	cout << "出现奇数次的元素为：" << num_2 <<" 和 "<< (num_1^num_2)<< endl;
    }
    
    //在一个其他数都出现 k 次的数组中找到只出现一次的数
    int KtoTen(int *arr, int k)
    {
    	int result = 0;
    	
    	int n = 1;
    	for (int i = 31; i >-1; --i)
    	{
    		result += arr[i] * n;
    		n = n*k;
    	}
    
    	return result;
    }
    void TentoK(int num, int *arr, int k)
    {
    	int i = 31;
    	while (num != 0)
    	{
    		arr[i--] = num % k;
    		num = num / k;
    	}
    }
    void XOr_K(int *result, int cur, int k)
    {
    	int cur_K[32] = { 0 };
    	TentoK(cur, cur_K, k);
    	for (int i = 31; i > -1; --i)
    	{
    		result[i] = (result[i] + cur_K[i]) % k;
    	}
    }
    int FindOnceTimeNum(int arr[], int n,int k)
    {
    	int result[32] = { 0 };
    	for (int i = 0; i < n; ++i)
    	{
    		XOr_K(result, arr[i], k);
    	}
    	
    	return KtoTen(result, k);
    
    }
    
    
    
    int main()
    {
    	// 不使用中间变量交换两个整数的值
    	//int a = 10, b = 5;
    	//cout << "a = " << a << ", b = " << b << endl;
    	//swap(a, b);
    	//cout << "a = " << a << ", b = " << b << endl;
    
    	// 整数的二进制表达中有多少个1
    	//int c = 27;
    	//cout << c << "的二进制表达中有" << number_of_one(c) << "个1" << endl;
    
    	//在一个整数数组中，只有1个数出现了奇数次，其余数都出现了偶数次，找出出现奇数次的数。
    	//int d[] = {1,2,3,4,5,10,1,2,3,4,5};
    	//cout << "出现奇数次的元素为：" << FindOddtimesNum(d, 11) << endl;
    	//在一个整数数组中，只有2个数出现了奇数次，其余数都出现了偶数次，找出出现奇数次的数。
    	//int e[] = { 1,2,3,4,5,10,64,1,2,3,4,5 };
    	//FindOddtimesNum_2(e, 12);
    
    	int F[] = { 1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,12,12,12,5 };
    	cout << "出现1次的元素为：" << FindOnceTimeNum(F, 19,3) << endl;
    
    	return 0;
    }