现在的位置: 首页 > 综合 > 正文

二进制中1的个数

2013年10月27日 ⁄ 综合 ⁄ 共 1659字 ⁄ 字号 评论关闭

算法中的位运算:二进制位运算共有五种运算。与、异或、或、左移、右移。运算规则如下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;
}

抱歉!评论已关闭.