4位先行进位电路 logisim_算法初探：位运算的应用

95 阅读 0 评论 63 点赞

我是靠谱客的博主疯狂水池，最近开发中收集的这篇文章主要介绍4位先行进位电路 logisim_算法初探：位运算的应用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

概念

位运算包括求与&、求或|、异或^、求反~

位运算的妙用

判断奇偶数：与1进行求与
异或可以理解为不进位的加法：1 + 1 = 0， 0 + 0 = 0， 1 + 0 = 1
（>>）右移，（<<）左移
(>>>) 逻辑右移，没有(<<<)
对于int，1<<35与1<<3是相同的。

例题

例题 1

可以通过异或运算解决。

比如a^b^a = b，也就是说两个相同的元素异或为0

所以，(1^2^3^k....^k^1000) ^(1^2^3^...^1000) = k，这样就找到了出现两次的元素。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int a[1001];
  for(int i=0;i<1000;i++)
    a[i] = i+1;
  a[1000] = rand()%1000 + 1;
  int index = rand()%1001;
  int temp = a[index];
  a[index] = a[1000];
  a[1000] = temp;
  for(int i=0; i<1001; i++)
    cout<<a[i]<<" ";
  cout<<endl;
  int x1=0;
  for(int i=1;i<1001;i++)
    x1 = x1^i;
  for(int i=0; i<1001; i++)
    x1 = x1^a[i];
  cout<<x1<<endl;

}

例题 2

共有三种解法：

将1左移32次（int类型有32位），与n的每一位求与，求与结果是1表明此位是1，否则此位是0.
将n右移32次（逻辑右移，高位补0），与1求与。
利用(n-1)&n的特性：相当于把n低位上的1去掉，每进行一次就消除了一个1.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    unsigned int n;
    cin>>n;
    cout<<bitset<sizeof(n)*4>(n)<<endl;

    int count = 0;

   // 将1左移32次，与n的每一位求与比较
    for(int i=0; i<32; i++)
    {
        if((n&(1<<i)) == (1<<i))
                count++;
    }
     cout<<count<<endl;
    count = 0;

    //将n逻辑右移32次，与1求与比较
    for(int i=0; i<32; i++)
    {
        if(((n>>i)&1)==1)
            count++;
    }
    cout<<count<<endl;

    count = 0;
    //(n-1)&n的效果相当于把n的最低位的1去掉
    while(n != 0)
    {
        n  = ((n-1)&n);
        count++;
    }
    cout<<count<<endl;
    return 0;

}

例题3

将整数的奇偶位（二进制）互换

解法：分别构造奇数位为0，偶数位为1和奇数位为1，偶数位为0的两个二进制串。

分别与整数求与，这样就分别提取除了整数二进制的偶数为与奇数位。

将偶数二进制从串右移，奇数二进制串左移，然后求或或者是求异或，即可得到奇偶位互换的结果。

#include <bits/stdc++.h>
using namespace std;
unsigned int m(unsigned int n)
{
    unsigned ji,ou;
    ou = n&0xaaaaaaaa;    //1010 1010 1010 1010
    ji = n&0x55555555;    //0101 0101 0101 0101
    return (ou>>1)|(ji<<1);
}
int main()
{
    unsigned int n;
    cin>>n;
    cout<<m(n)<<endl;
    return 0;

}

例题4

#include <bits/stdc++.h>
using namespace std;
int main()
{
    double num;
    cin>>num;
    string s="0.";
    while(num != 0.0)
    {
        //乘2 挪整
        num *= 2;
        //判断整数部分
        if(num >= 1)
        {
            s.append("1");
            //消除整数
            num -= 1.0;
        }
        else
            s.append("0");

        if(s.size()>34)
        {
            cout<<"ERROR"<<endl;
            break;
        }
    }
    if(s.size()<=34)
        cout<<s<<endl;
    return 0;
}