算法-位运算

思路：
将原始数组和添加重复数字的数组相抑或，最后的结果就是重复的数字。

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(void) {
	int arr[1001] = {};
	srand((int)time(0)); 
	for(int i=0; i<1000; i++){
		arr[i] = i + 1;
	}
	arr[1000] = (rand()%1000) + 1;
	int index = (rand()%1000);
	
	arr[index] = arr[1000]^arr[index];
	arr[1000] = arr[1000]^arr[index];
	arr[index] = arr[1000]^arr[index];
	
	for(int i=0;i<1001;i++){
		cout<<arr[i]<<" ";
	}
	int x = 0;
	/*
	for(int i=1; i<=10;i++){
		x = x^i;
	}
	*/
	for(int i=0;i<1001;i++){
		x = x^arr[i]^i;
	}
	cout<<endl;
	cout<<x<<endl;
	return 0;
}

思路：直接挨个遍历。

思路1：不断右移并且判断最后一位是否为一。

#include <iostream>
using namespace std;
int main(void) {
	int num = 0;
	cin>>num;
	int res = 0;
	while(num){
		if(num&1)
			res++;
		num = num>>1;
	}
	cout<<res<<endl;
	return 0;
}

思路2:每次利用减一，然后被减数和结果相与，知道为零，循环次数就是一的个数。

#include <iostream>
using namespace std;
int main(void) {
	int num = 0;
	cin>>num;
	int res = 0;
	while(num){
		num = num & (num-1);
		res++;
	}
	cout<<res<<endl; 
	return 0;
}

思路：就是问二进制表示中是不是只有一个1，利用上一题思路直接出结果。

#include <iostream>
using namespace std;
int main(void) {
	int num = 0;
	cin>>num;
	int res = 0;
	while(num){
		num = num & (num-1);
		res++;
		if(res>1){
			break;
		}
	}
	cout<<(res==1)<<endl; 
	return 0;
}

思路： 取出奇数位偶数维，奇数位右移，偶数位左移，结果再相或。

#include <iostream>
#include <cstdio>
using namespace std;
int main(void) {
	int input = 0;
	int res = 0;
	cin>>input;
	int even = 0xaaaa;
	int odd = 0x5555;
	odd = input&odd;
	even = input&even;
	res = (odd<<1)|(even>>1);
	cout<<res<<endl;
	return 0;
}

思路：乘2取整

#include <iostream>
#include <math.h>
using namespace std;
int main(void) {
	char res[34] = {'0','.'};
	double input = 0;
	cin>>input;
	int times = 0;
	while(input>0){
		times++;
		if(times>32) break;
		input = input*2;
		if(input>=1){
			input--;
			res[times+1] = '1';
			continue;
		}
		res[times+1] = '0';
	} 
	if(input) cout<<"ERROR"<<endl;
	else for(int i = 0; i < 34; i++) cout<<res[i];
	return 0;
}

思路：k个k进制数字进行不进位加法结果为零。
先将数组中的数转换成k进制放入string存储，对其长度，逐位进行不进位加法，最终得出的结果再转换成十进制输出。

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
using namespace std; 
/*
*	将传入的数字转换成base进制的数 
*/ 
string decTok(int dec,int k);

/*
*	将k进制转换成十进制 
*/
int kTodec(string ans,int k);


int main(void) {
	//k个k进制的数进行不进位加法，结果为零 
	int k = 3;
	int maxlen = 0;
	int nums[] = {1,1,1,3,3,3,5,5,5,9,6,6,6,7,7,7 };	
	string str[16];	
	for(int i = 0; i < 16; i++){
		str[i] = decTok(nums[i],k);
	}
	for(int i = 0; i < 16; i++){
		int len = str[i].size();
		maxlen = max(maxlen,len);
	}
	for(int i = 0; i < 16; i++){
		while(str[i].size() < maxlen){
			str[i] = "0" + str[i];
		}
	}
	
	//初始化结果字符
	string ans (maxlen,'0');
	for(int i = 0; i < 16; i++){
		for(int j = 0; j < maxlen; j++){
			ans[j] = char(((str[i][j] - '0') + (ans[j] - '0')) % k + '0');
		}
	}
	
	cout<<kTodec(ans,k)<<endl;
	return 0;
}



int kTodec(string ans,int k){
	int times = ans.size() - 1;
	int res = 0;
	for(int i = 0; i < ans.size(); i++){
		res += (ans[i]-'0') * pow(k,times--);
	}
	return res;
}


string decTok(int dec,int k){
	string ret = "";
	while(dec){
		ret += char(dec%k + '0');
		dec /= k;
	}
	reverse(ret.begin(),ret.end());
	return ret;
}