算法中的位运算:二进制位运算共有五种运算。与、异或、或、左移、右移。运算规则如下m<<n 表示把m左移n位,左移n位的时候,最左边的n为将被丢弃同时在最右边补上n个0.
00001010<<2 = 00101000
10001010<<3 = 01010000
m>>n表示把m右移n位,右移n为的时候,最右边的n位将被丢弃。但右移时处理左边的位将会复杂一点,如果数字是一个无符号数值,则用0填补最左边的n位,如果数字是一个有符号的数值,则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数,则右移之后再最左边补0,如果数字原先是一个负数,则右移之后在左边补n个1.
00001010>>2 = 00000010
10001010>>3 = 11110001
1.求二进制中1的个数
#include<iostream>
using namespace std;
int NumberOf1(int);
int main()
{
// int number;
// cin>>number;
for(int i=0;i<1000;i++)
cout<<NumberOf1(i)<<endl;
return 0;
}
int NumberOf1(int n)
{
int count=0;
while(n)
{
if(n&1)
count++;
n=n>>1;
}
return count;
}
上面的代码存在一个问题:如果输入的N为负数,则会发生死循环。以为之前为负数,以为之后要保持符号,所以最高位仍为1,如果整个数字一直做右移运算,最终数字会变成0XFFFFFFFF而陷入死循环。
为了避免死循环,我们可以不右移输入的数字。首先将n和1做运算,即先判断最低位,然后在左移1,判断n的第二位,然后判断第三位....
代码如下:
int NumberOf1(int n) { int count=0; unsigned int flag=1; while(flag) { if(n&flag) count++; flag=flag<<1; } //每次判断n中的一位 return count; }
十进制转换成二进制:
#include<iostream> #include<stack> using namespace std; void Transfer(int n,stack<int> &Stack); int main() { int number; stack<int> Stack; cin>>number; Transfer(number,Stack); while(Stack.size()) { cout<<Stack.top(); Stack.pop(); } cout<<endl; return 0; } void Transfer(int n,stack<int> &Stack) { if(n==0) Stack.push(0); while(n) { Stack.push(n%2); n=n/2; } }</span>
绝对值:
#include<iostream> using namespace std; int Abs(int n); int main() { cout<<Abs(3)<<endl; cout<<Abs(-344)<<endl; cout<<Abs(543)<<endl; cout<<Abs(-1)<<endl; return 0; } int Abs(int n) { int i=n>>31; cout<<"I的值为"<<i<<" "; if(i==0) return n; if(i==-1) return (~n)+1; }
使用位操作交换两个数(不适用中间变量):
void Swap(int& a,int& b) { a^=b; b^=a; //相当于 b=b^(a^b) x^x=0; a^=b; //a=(a^b)^b; 同上.异或满足交换律 }
判断奇偶性:
#include<iostream> using namespace std; int main() { for(int i=0;i<100;i++) { if(i&1) cout<<i<<"是奇数"<<endl; else cout<<i<<"是偶数"<<endl; } return 0; }