精华内容
下载资源
问答
  • 编写函数 unsigned int reverse_bits(unsigned int value) 这个函数的返回值是把value的二进制位模式从左到右变换后的值, 如在32机器上,25的二进制表示为00000000 00000000 00000000 00011001 函数返回值应该是...

    编写函数

    
    unsigned int reverse_bits(unsigned int value)

    这个函数的返回值是把value的二进制位模式从左到右变换后的值,

    如在32位机器上,25的二进制表示为00000000 00000000 00000000 00011001

    函数返回值应该是: 10011000 00000000 00000000 00000000,十进制就是2550136832

    注意不要依赖机器上整型值的长度。

    该题也是LeetCode 190题,要解决本题,需要熟练掌握二进制位的含义,移位操作等。

    • 算法1:

    这个是最容易想到的,首先使用 value &1 取得最后一位,然后 result << 1 左移一位,保留上一次的最后一位,再和 ( value &1 ) 或操作取得这一次的 result, value再右移,取得下一高位数据,直到取完所有位。

    unsigned int reverse_bits(unsigned int value) {
        unsigned int result = 0;
        int bits = sizeof(unsigned int) * 8;
        printf("bits : %d\n", bits);
        for (int i = 0; i < bits; i++) {
                result = (result << 1) | (value & 1);
                value >>= 1;
        }
        return result;
    }
    
    
    int main() {
        unsigned int a = 0b00011001 ;//25
        a = reverse_bits(a);
        printf("%u", a);
        return 0;
    }
    
    • 由于要求不依赖与机器位数,所以可以定义uint32_t.,然后改写一下:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; i++) {
                result = (result << 1) | (n & 1);
                n >>= 1;
        }
        return result;
    }
    • for循环中的操作也可以改写为如下方式:
    uint32_t reverseBits(uint32_t n) {
            int result=0;
    		for (int i = 0; i < 32; i++) {
    			uint32_t n_last_bit = n & 1;//获取n最低位
    			uint32_t tmp = n_last_bit<<(31-i);//将n的最低位移动到相对应的翻转位置
    			result |= tmp; // 保留结果
    			n >>= 1;
    		}
    		return result;
    
    }

    这2种方式翻转保留数据的方式不一样,一个是result保留在最低位,左移,又保存新值,另一个是直接更新到指定的翻转位,然后和上一次的result或操作,2种方式都可以实现,但第二种或多一个或操作,所以前一种方式更优。

     

    • 复杂度分析

    1、时间复杂度:\mathcal{O}({1}),在算法中循环次数是固定的,不论输入什么,都是32位。
    2、空间复杂度:\mathcal{O}(1),因为不管输入是什么,内存的消耗是固定的。

    这里可以改写for循环,使用while循环替代for循环,时间复杂度将变为\mathcal{O}(\log_2{N})

    uint32_t reverseBits(uint32_t n) {
        uint32_t ret = 0, power = 31;
        while (n != 0) {
          ret += (n & 1) << power;
          n = n >> 1;
          power -= 1;
        }
        return ret;
    }

    我们可以发现,当数据比较小的时候,32位的前面3个字节高位全部是0,当n不断右移的时候,如果低位取出每次的最低位后n就变成了0,这个时候就没有必要再继续循环翻转了。每次给result赋值的时候也是把数据直接移动响应的翻转位,其他低位都是0,所以并不影响翻转结果,这样大大节省了循环次数。时间复杂度为\mathcal{O}(\log_2{N})

    大家可以对比以下时间复杂度得曲线,可以看出差异。

     

    • 算法2: 

    还有没有更好的办法呢? 答案是肯定的,这里就来看一下算法中经常使用的方法:分治合并。

    因为固定32位,翻转对称,所以可以分成2个16位翻转,每个16位又分别分成2个8位翻转...依次类推,最后翻转2位,然后合并翻转结果。具体步骤详见代码和注释。

    void print_binary(unsigned int number) {
        if (number >> 1) {
            print_binary(number >> 1);
        }
        putc((number & 1) ? '1' : '0', stdout);
    }
    
    int reverse_bits(uint32_t n) {
        //左右16位翻转
        n = (n >> 16) | (n << 16);
        print_binary(n);
        printf("\n");
    
        //用0xff00ff00即11111111 00000000 11111111 00000000与n与运算取出左右两边高8位
        //用0x00ff00ff即00000000 11111111 00000000 11111111与n与运算取出左右两边低8位
        //利用左移和右移翻转后用或运算合并
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
        print_binary(n);
        printf("\n");
    
        //利用0xf0f0f0f0即11110000 11110000 11110000 11110000与n与运算取出每一个字节的高4位
        //利用0x0f0f0f0f即00001111 00001111 00001111 00001111与n与运算取出每一个字节的低4位
        //利用左移和右移翻转后用或运算合并
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
        print_binary(n);
        printf("\n");
    
        //利用0xcccccccc即11001100 11001100 11001100 11001100与n与运算取出每4位中的前2位
        //利用0x33333333即00110011 00110011 00110011 00110011与n与运算取出每4位中的后2位
        //利用左移和右移翻转后用或运算合并
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
        print_binary(n);
        printf("\n");
    
        //利用0xaaaaaaaa即10101010 10101010 10101010 10101010与n与运算取出每2位中的前1位
        //利用0x55555555即01010101 01010101 01010101 01010101与n与运算取出每2位中的后1位
        //利用左移和右移翻转后用或运算合并
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
        print_binary(n);
        printf("\n");
    
        return n;
    }
    
    int main() {
        int num = 0b00101011101100011110000110101001;
        printf("Num:%u\n", num);
        print_binary(num);
        printf("\nReverse:\n");
    
        num = reverse_bits(num);
    
        printf("Reverse result: %u\n", num);
        print_binary(num);
    }
    

    输出结果:

    Num:733077929
    101011101100011110000110101001
    Reverse:
    11100001101010010010101110110001
    10101001111000011011000100101011
    10011010000111100001101110110010
    1101010010010110100111011101000
    10010101100001111000110111010100
    Reverse result: 2508688852
    10010101100001111000110111010100

    复杂度分析

    • 时间复杂度:\mathcal{O}(1)
    • 空间复杂度:\mathcal{O}(1)

     

    • Java 的整形类Integer有一个reverse方法就是采用的这个算法思想:
       /**
         * Returns the value obtained by reversing the order of the bits in the
         * two's complement binary representation of the specified {@code int}
         * value.
         *
         * @param i the value to be reversed
         * @return the value obtained by reversing order of the bits in the
         *     specified {@code int} value.
         * @since 1.5
         */
        public static int reverse(int i) {
            // HD, Figure 7-1
            i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
            i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
            i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
            i = (i << 24) | ((i & 0xff00) << 8) |
                ((i >>> 8) & 0xff00) | (i >>> 24);
            return i;
        }

    我们可以看到Java JDK源码中的实现思路和上面我们的算法一致,略有不同的是:

    第一步,先相邻位置翻转。

    第二步再相邻2位一起翻转。

    第三步再相邻4位一起翻转。

    最后:A. 通过左移24位把低位字节第0-7位移动到高位第23-31位.。

              B.通过与0xff00与操作取得第8-15位再左移8位到第16-23位。

              通过这AB两步就取得了结果的高16位,然后同理:

              C.通过右移8位然后与0xff00与操作,取得第16-23位。

              D.右移24位取得最高位,

              E.CD两步或操作就取得了结果的低16位,再与AB取得的结果高16位进行或运算即可得到最终的翻转结果。

    该问题也是C语言面试中经常被考察的问题,对二进制数据的位移操作,与或操作的理解很有帮助。

    展开全文
  • 二进制位翻转:

    2016-06-03 15:50:30
    思路: 利用按与(&)求得二进制每一的数字,然后再与ret 进行 按或(|) 运算。 ret左移,value右移 ...//二进制位进行翻转 #include #include unsigned int reverse_bit(unsigned int value) { u

    题目:使用c语言编写函数:

    unsigned int reverse_bit(unsigned int value);

    这个函数的返回值value的二进制位模式从左到右翻转后的值

    思路:

    利用按位与(&)求得二进制每一位的数字,然后再与ret 进行 按位或(|)   运算。  ret左移,value右移



    //unsigned int reverse_bit(unsigned int value);
    //二进制位进行翻转
    
    #include<stdio.h>
    #include<stdlib.h>
    unsigned int reverse_bit(unsigned int value)
    {
    	unsigned int ret = 0;
    	for (int i = 0; i < 32; i++)
    	{
    		ret = ret << 1;
    		unsigned bit = value & 1;
    		value =value>> 1;
    		ret |= bit;
    	}
    	return ret;
    }
    
    int main()
    {
    	unsigned int value = 0;
    	scanf("%d", &value);
    	unsigned int  ret=reverse_bit(value);
    	printf("%u\n", ret);
    
    	system("pause");
    	return 0;
    }


    展开全文
  • 二进制翻转

    千次阅读 2019-05-31 08:20:52
    这个函数的返回值是value的二进制位模式从左到右翻转后的值。 如: 在32机器上25这个值包含下列各位: 00000000000000000000000000011001 翻转后:(2550136832) 10011000000000000000000000000000 程序结果返回...

    编写函数:
    unsigned int reverse_bit(unsigned int value);
    这个函数的返回值是value的二进制位模式从左到右翻转后的值。
    如:
    在32位机器上25这个值包含下列各位:
    00000000000000000000000000011001
    翻转后:(2550136832)
    10011000000000000000000000000000
    程序结果返回:
    2550136832
    方法1:将二进制的位数从右往左拿下每一位,
    然后乘以从左到右的权值然后相加得到。

    #include<stdio.h>
    #include<Windows.h>
    #include<math.h>
    #pragma warning (disable :4996)
    unsigned int reverse_bit(unsigned int value)
    {
        unsigned int sum = 0;
        int i = 0;
        int count = 32;
        for (i = 0; i<32; i++)
         {
            if ((value>>i) & 1 == 1)
             {
                count--;
                sum += pow(2,count);
             }
             else
              {
                  count--;
              }
         }
          return sum;
    }
    unsigned int reverse_bit1(unsigned int value)
    {
     unsigned int sum = 0;
     int i = 0;
     for (i = 0; i<32; i++)
     {
      sum += ((value  >> i) & 1)*pow(2, 31 - i);//优化
      return sum;
    }
    int main()
    {
     unsigned int num =0;
     unsigned int result = 0;
     scanf("%d", &num);
     result=reverse_bit(num);
    printf("%u\n", result);//要以无符号数打印,
     如果最后一位是1,交换号会变成负数打印
     system("pause");
     return 0;
    }
    

    方法二:首先,创建变量ret,ret为翻转后的数,
    将他初始化为0.然后从右往左取下value二进制的
    每一位按位或到ret上,在把ret向左移移位。

    unsigned int reverse_bit(unsigned int value)
    {
     int i = 0;
     int ret = 0;
     for (i = 0; i < 32; i++)
     {
      ret <<= 1;
      ret |= ((value >> i) & 1); //任何数和0按位或都是它本身
     }
     return ret;
    }
    int main()
    {
     unsigned int num =0;
     unsigned int result = 0;
     scanf("%d", &num);
     result=reverse_bit(num);
     printf("%u\n", result);//要以无符号打印,
     如果最后一位是1,交换号会变成负数打印
     system("pause");
     return 0;
    }
    
    展开全文
  • 问题1: 将某数的二进制中各位翻转 unsigned char reverse8( unsigned char c ) { c = ( c & 0x55 ) | ( c & 0xAA ) >> 1; c = ( c & 0x33 ) | ( c & 0xCC ) >> 2; c = ( c & 0x0F ) | ( c & 0xF0 ) >> 4; ...

    本帖转自http://blog.csdn.net/todototry/archive/2007/04/23/1575900.aspx

    但是更加详细的说明如下:

    这两个函数极很是巧妙,作了并行计算。

    问题1: 将某数的二进制中各位翻转

    unsigned char reverse8( unsigned char c )
    {
        c = ( c & 0x55 ) << 1 | ( c & 0xAA ) >> 1;
        c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
        c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
        return c;
    }

    unsigned int Bit_Reverse(unsigned int v)
    {
        v = ((v >> 1) & 0x55555555) | ((v << 1) & 0xaaaaaaaa);
        v = ((v >> 2) & 0x33333333) | ((v << 2) & 0xcccccccc);
        v = ((v >> 4) & 0x0f0f0f0f) | ((v << 4) & 0xf0f0f0f0);
        v = ((v >> 8) & 0x00ff00ff) | ((v << 8) & 0xff00ff00);
        v = ((v >> 16) & 0x0000ffff) | ((v << 16) & 0xffff0000);
        return v;
    }


    算法是这样的: 首先是2位2位为一组,交换前一半和后一半。再4位4位为一组,交换前一半和后一半。再8位为一组,交换前一半和后一半。

    可能还有点说不清楚。我举个例子。
    将1 2 3 4 5 6 7 8 反转。
    (1)2个2个为一组,交换前一半和后一半, 变成。
       2 1 4 3 6 5 8 7
    (2)4个4个为一组,交换前一半和后一半, 变成
       4 3 2 1 8 7 6 5
    (3)再8个为一组,交换前一半和后一半, 变成
       8 7 6 5 4 3 2 1
    反转成功。
    这样的算法本来很是简单,很容易用数学归纳法证明其正确。这函数, 巧妙就巧妙在作了并行计算,分组,它一次就计算完了。

    先看第一个语句。c = ( c & 0x55) << 1 | ( c & 0xAA ) >> 1; 
    0x55其实就是01010101, 0xAA就是10101010
    假设 c=abcdefgh
    c & 0x55 = 0b0d0f0h,     c & 0xAA = a0c0e0g0
    跟着,前者左移一位, b0d0f0h0, 后者右移一位, 0a0c0e0g, 再一个|运算,就两位两位交换了位置。
    想象一下,你有一个长纸条,分成一格一格,每格写一个字,假如你将纸条每隔一格剪一个小洞,滑一格,覆盖在原来的纸条上,你就会看到两个两个字交换了位置。
    (注: |运算可以换成+运算,想一想为什么)

    第二个语句。 c = ( c & 0x33 ) << 2 | ( c & 0xCC ) >> 2;
    0x33 = 00110011, 0xCC=11001100。

    第三个语句。c = ( c & 0x0F ) << 4 | ( c & 0xF0 ) >> 4;
    0x0f = 00001111, 0xF0=11110000.

    这两个语句的作用也是 分组,将一半位变成0,移位滑动,跟着再组合,就分组交换了位置。
    不防想象两个小纸条剪洞叠加。

    这方法应该可以推广。

    理解了问题1,也就很容易理解问题2了.


    问题2: 判断32位整数二进制中1的个数。

    unsigned long func(unsigned long x)
    {
        x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL);
        x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL);
        x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL);
        x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL);
        x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL);
        return x;
    }

    和问题1一样,也是采用了分组并行计算。

    基本方法是: 2位2位为一组,相加,看看有几个1。再4位4位为一组,相加,看看有几个1......
    还是说的不太明白。接着分析。

    为了简单说明,先看看8位的情形。相应地,函数里面的语句变成。
    x = (x & 0x55) + ((x >> 1) & 0x55);    (1)
    x = (x & 0x33) + ((x >> 2) & 0x33);    (2)
    x = (x & 0x0f) + ((x >> 4) & 0x0f);    (3)
    return x;

    假设x=abcdefgh. 0x55=01010101
    x & 0x55 = 0b0d0f0h.   (x>>1) & 0x55 = 0a0c0e0g。相加。就可以知道2位2位一组1的个数。

    比如x=11111111
    x= (x & 0x55) + ((x >> 1) & 0x55); 之后x=10101010。你2位2位地看,10=2, 就是2 2 2 2, 就是说各组都是2个1。
    比如x=00101001
    x= (x & 0x55) + ((x >> 1) & 0x55); 之后x=00010101。你2位2位地看,就是0 1 1 1, 前1组只有0个1,后面的组都是1个1。

    好啦。再来看。0x33=00110011。
    x=abcdefgh. 
    x=(x & 0x33)+((x >> 2)&0x33); 相当于, 00ab00ef + 00cd00gh。
    因为语句(1)之后。ab指示了头两位有多少个1,cd指示了下两位有多少个1。相加00ab+00cd就指示前4位有多少个1。这样就是4位4位为一组。注意这样的分组,组与组之间永远都不会产生进位的。正因为不会产生进位,才可以分开来看。

    好啦。下面的过程都是一样的,不再多说。
    8位,16位,32位都一样。


    展开全文
  • 今天来练习一下,对一个数的二进制数进行翻转,求出翻转后的二进制数对应的十进制数值。 即:原数据的二进制序列为 00000000000001010 经过翻转后的序列变成了 11111111111110101 求出这个新的二进制序列对应的十...
  • c语言实现二进制位从左到右进行翻转 问题说明: 如: 在32机器上25这个值包含下列各位: 00000000000000000000000000011001 翻转后:(2550136832) 10011000000000000000000000000000 程序结果返回: ...
  • 在32机器上25这个值包含下列各位: 00000000000000000000000000011001 翻转后:(2550136832) 10011000000000000000000000000000 程序结果返回: 2550136832 #include &amp;lt;stdio.h&amp;gt; ...
  • 主要介绍了C++二进制翻转,通过几个实例分析二进制翻转算法的实现技巧,需要的朋友可以参考下
  • #include<stdio.h> unsigned int reverse_bit(unsigned int x) {  int value = 0;  int i = 0;  for (i = 0; i < 32; i++)  {   if (x &...{...
  • 本文实例讲述了C++二进制翻转的方法,将常用的几种解决方法罗列出来供大家比较选择。具体如下: 首先来看看一个相对笨拙的算法: #include <iostream> using namespace std; void printBinary...
  • 二进制位翻转

    千次阅读 2013-08-03 23:15:21
    今天看到python中讲到按位翻转~x=-(x+1),其原理应该是二进制翻转,网上查到一段解释听清楚的。 简单的说例如1用32位二进制存储的结果是 00000000000000000000000000000001 这是二进制,不是十进制哦,那么求...
  • #include<stdlib.h> #include<stdio.h> #include<...unsignedintreserve_bit(unsignedintnum)//采用移位的方法使一个数的二进制位翻转后返回 { unsignedintret=0; intbit=0; inti=...
  • 二进制的左右翻转

    千次阅读 2019-01-22 22:28:13
    这个函数的返回值value的二进制位模式从左到右翻转后的值。 在32机器上25这个值包含下列各位: 00000000000000000000000000011001 翻转后:(2550136832) 10011000000000000000000000000000 程序结果返回:...
  • ////这个函数的返回值value的二进制位模式从左到右翻转后的值。 //// ////如: ////在32机器上25这个值包含下列各位: ////00000000000000000000000000011001 ////翻转后:(2550136832) ////...
  • 颠倒给定的 32 无符号整数的二进制位。 示例: 输入: 43261596 输出: 964176192 解释: 43261596 的二进制表示形式为 00000010100101000001111010011100 ,  返回 964176192,其二进制表示形式为 ...
  • matlab 将二进制反转

    千次阅读 2020-05-25 17:15:02
    原始序列 :0 1 0 1 0 1 1 1 转换后序列:1 1 1 0 1 0 1 0 dec2bin(234) ans = 0 1 0 1 0 1 1 1 fliplr(ans) ans = 1 1 1 0 1 0 1 0 de2bi(234, ‘left-msb’) ans = 1 1
  • 一个数的二进制是由组成,我们需要对它的每一进行操作。 第一位翻转:20 —&amp;amp;gt; 2(31-0) 第二位翻转:21 —&amp;amp;gt; 2(31-1) 第三位翻转:22 —&amp;amp;gt; 2(31-2) 第 i 位翻转:...
  • 二进制反转

    千次阅读 2019-05-27 15:58:38
    请编写函数,这个函数的返回值是把value的二进制位模式从左到右变换一下后的值。例如,在32机器上,25这个值包含下列各个: 000000000000000000000000000000011001 函数的返回值应该是2550136832,它的二级制...
  • c小白,求助大佬。![图片](https://img-ask.csdn.net/upload/201703/24/1490353309_605380.png)
  • BUPT 2018 计算机 ProblemA | 二进制和十进制相互转化算法
  • 今天分享一个二进制...这个函数的返回值value的二进制位模式从左到右翻转后的值。 如: 在32机器上25这个值包含下列各位: 00000000000000000000000000011001 翻转后:(2550136832) 100110000000000000000000...
  • 二进制位翻转函数

    2019-04-23 19:14:31
    二进制位翻转函数 编写函数: unsigned int reverse_bit(unsigned int value); 这个函数的返回值是value的二进制位模式从左到右翻转后的值。 如: 在32机器上25这个值包含下列各位: ...
  • 例如一个二进制数是 0000 0000 0000 1100 我们的工作是将其反转为 0011 0000 0000 0000 我们当然可以从最低与出每一数, 然后从最高开始排列下去. 但这里有一个更迅速的办法 假设我们要将 ...
  • 理论基础: >> :右在这里插入代码片移 << :左移 ...偶数 左移1===> 然后 进行 | 运算) 奇数:通过 A 与 1010 1010(0xaa) 进行 与(&)运算 //这是提取奇数 ==> (a&
  • 二进制位运算符

    2021-10-08 11:21:45
    二进制位运算符用于直接对二进制位进行计算,一共有7个。 二进制或运算符(or):符号为|,表示若两个二进制位都为0,则结果为0,否则为1。 二进制与运算符(and):符号为&,表示若两个二进制位都为1,则结果...
  • 要求:在32机器上25这个值包含下列各位: 00000000000000000000000000011001 翻转后:(2550136832) 10011000000000000000000000000000 程序结果返回: 2550136832#include&lt;stdio.h&gt; #include&...
  • Python实现"颠倒二进制位"的两种方法

    千次阅读 2018-09-12 20:02:22
    翻转给定的32无符号整数的二进制位 Example: Input: 43261596 Output: 964176192 Explanation: 43261596 represented in binary as 00000010100101000001111010011100,  return 964176192 represented in ...
  • 颠倒给定的 32 无符号整数的二进制位。 提示: 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 27,869
精华内容 11,147
关键字:

二进制位翻转