精华内容
下载资源
问答
  • 翻转二进制

    2017-12-21 11:29:53
    这个函数的返回 值value的二进制位模式从左到右翻转后的值 如: 在32位机器上25这个值包含下列各位: 00000000000000000000000000011001 翻转后:(2550136832) 10011000000000000000000000000000 ...

    编写函数: unsigned int reverse_bit(unsigned int value); 这个函数的返回 值value的二进制位模式从左到右翻转后的值
    如:
    在32位机器上25这个值包含下列各位:
    00000000000000000000000000011001
    翻转后:(2550136832)
    10011000000000000000000000000000
    程序结果返回:
    2550136832
    提问:如何得到二进制数的每一位,怎么将其反转

    #include<stdio.h>
    unsigned int reverse_bit(unsigned int value)
    {
        unsigned int sum = 0;
        int i = 0;
        for (i = 0; i < 32; i++)
        {
            sum += ((value >> i) & 1) << (31 - i);//例如右移0位按位与一得到最低位,再把得到的二进制数左移31位,这就翻转了最低位,其余的数字同理操作
        }
        return sum;
    
    }
    
    int main()
    {
        unsigned int num = 25;
        printf("翻转后:%u\n", reverse_bit(num)); 
        return 0;
    }
    展开全文
  • 每天 3 分钟,走上算法的逆袭之路。...题目:翻转二进制数 题目来源:https://leetcode-cn.com/problems/reverse-bits/ 颠倒给定的 32 位无符号整数的二进制位。 示例 1: 输入: 000000101001010000011110..

    每天 3 分钟,走上算法的逆袭之路。

    前文合集

    每日一道 LeetCode 前文合集

    代码仓库

    GitHub: https://github.com/meteor1993/LeetCode

    Gitee: https://gitee.com/inwsy/LeetCode

    题目:翻转二进制数

    题目来源:https://leetcode-cn.com/problems/reverse-bits/

    颠倒给定的 32 位无符号整数的二进制位。

    示例 1:

    输入: 00000010100101000001111010011100
    输出: 00111001011110000010100101000000
    解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596,
         因此返回 964176192,其二进制表示形式为 00111001011110000010100101000000。
    

    示例 2:

    输入:11111111111111111111111111111101
    输出:10111111111111111111111111111111
    解释:输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293,
         因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。
    

    提示:

    • 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
    • 在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 2 中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825。

    解题方案一:暴力翻转

    常规的线型思维是拿到一个数,直接翻转就好了,比如下面这样:

    这么干看起来简单,实际上并不是那么好实现。

    • 比如一个数 001 ,我们翻转以后的结果是 1 ,并不会是 001 ,前面的 0 会省去。
    • 这种方案还需要考虑是否会整形溢出, Java 的整数溢出后的二进制数会表示成负数。

    这就很坑了,由于是二进制数,解决方案可以使用移位运算,而不是除法运算。

    先定义一个结果 res 为 0 ,然后对 110 进行翻转操作,把每一步的结果都存在 res 中,最后得到的 res 就是我们想要的结果。

    第一步:
    res 左移一位,res = 0
    110 的最低位为 0 ,加到 res 上,结果为 0 
    110 右移一位,结果为 11
    
    第二步:
    res 左移一位,res = 0
    11 的最低位为 1 ,加到 res 上,结果为 1
    11 右移一位,结果为 1
    
    第三步:
    res 左移一位,res = 10
    1 的最低位为 1 ,加到 res 上,结果为 11
    1 右移一位,结果为 0 ,操作结束
    

    第一个问题来了,如何获取 n 的最低位?

    可以使用位运算的 & ,使用 (n & 1) 可以得到 n 的最低位,原理的话我就不说了,看不懂的可以查查位运算 & 是如何计算的。

    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            // 获取 n 的最低位加到 res 上
            res = (res << 1) + (n & 1);
            // n 右移一位
            n >>= 1;
        }
        return res;
    }
    

    这感觉第一步就结束了啊,直接超过 100% 了,不管那么多,接着往下看答案还是。

    解题方案二:分治合并

    答案上这个方案简直秀到家了,从第一眼看一脸懵逼,到后面打断点一步一步看下来赞叹不已,只留下大写的 「牛逼」 两个字。

    先放代码,我觉得大多数人第一眼看到代码的人都是一脸懵。

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

    看到这段代码我第一个感觉是:我是谁?我在哪?我去哪?

    人称三大哲学问题。

    这个解题思路是这样的:

    • 总共 32 个数,先把这 32 个数从中间拆分成 2 组,每组 16 个数,然后反转这两组进行合并。
    • 然后再把 16 个数拆分成 2 组,每组 8 个数,再反转这两组合并。
    • 接着进行查分,直至拆分成每组 1 个数,然后进行反转合并。

    我知道,配合这段解释大多数人还是看不懂,我就用题上的一个数举例子吧,人肉帮你们 debug 一下:

    第一次拆分,是通过两个 16 进制的数进行的,分别是 0xffff00000x0000ffff ,这两个数如果转换成 2 进制的结果如下:

    0b11111111_11111111_00000000_00000000
    0b00000000_00000000_11111111_11111111
    

    实际上第二个数前面的 0 是应该省略掉的,方便理解我手动补 0 。

    • 第一次进行了位运算的 & 运算,相当于直接取到了左边的 16 个数字和右边的 16 个数字。
    • 然后对得到的结果分别进行位移操作,左边的结果进行右移 16 位,右边的结果左移 16 位。
    • 接下来使用 | 将左右两边的结果合并起来。
    • 使用一些有规律的 16 进制的数,分别取到左右 8 位,左右 4 位,左右 2 位 和左右 1 位,进行反转合并。
    • 重复这个过程,最终就得到了整个二进制数的反转后的结果。

    注意: >>> 在 Java 的含义是无符号位移,无论是正数还是负数,高位通通补 0 。

    这是一个无需循环就能原地翻转二进制数的方案,真心是服了啊,不过感觉在如果是在面试中出这道题,进行 & 操作的时候这些 16 进制数不大好写,直接写 2 进制可能来的更为简单一点。

    您的扫码关注,是对小编坚持原创的最大鼓励:)
    展开全文
  • 翻转二进制

    2019-10-05 09:30:17
    uint32_t reverseBits(uint32_t n) { auto strBits = bitset<32>(n).to_string(); return static_cast<uint32_t>(bitset<...(string(strBits.crbegin(), strBits.crend())).to_u...
    uint32_t reverseBits(uint32_t n) {
        auto strBits = bitset<32>(n).to_string();
        return static_cast<uint32_t>(bitset<32>(string(strBits.crbegin(), strBits.crend())).to_ulong());
    }

     

    转载于:https://www.cnblogs.com/wuOverflow/p/4711207.html

    展开全文
  • 题目 给出n行m列的0、1矩阵,每次操作可以将任意一行或一列反转,即这一行或一列中0变为1,1变为0。问通过任意多次这样的变换...这里我用二进制枚举,建议用二进制枚举时数组从0开始,方便后面枚举。 AC代码 #include &

    题目

    给出n行m列的0、1矩阵,每次操作可以将任意一行或一列反转,即这一行或一列中0变为1,1变为0。问通过任意多次这样的变换,最多可以使矩阵中有多少个1。
    N >= 10 M <= 10000

    题解思路

    行比较少,我们可以枚举行的变换来确定列。
    当列的1数目大于一半时不翻转,小于等于时翻转,等于翻转就涉及到奇数取整的问题,例如 1 3 3/2 = 1 .但如果翻转了就是2了,所以等于也要翻转。

    这里我用二进制枚举,建议用二进制枚举时数组从0开始,方便后面枚举。

    AC代码

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int mp[12][10010];
    int main ()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            if (n == 0 )
                break;
            int ans = 0 ;
            for (int i = 1 ; i <= n ; i++ )
            {
                for (int j = 1 ; j <= m ; j++ )
                {
                    scanf("%d",&mp[i][j]);
                }
            }
            for (int i = 0 ; i< 1<<n ; i++  )
            {
                int t = 0 ;
                for (int j = 1 ; j <= m ; j++ )
                {
                    int p = 0 ;
                    for (int k = 1 ; k <= n ; k++ )
                    {
                        if ( mp[k][j] == 1 )
                        {
                            if ( !(i >>(k-1) & 1))
                                p++;
                        }else
                        {
                            if (i >>(k-1) & 1)
                                p++;
                        }
                    }
                    if ( p <= n/2 )
                        p = n - p;
                    t+= p;
                }
                ans = max(ans,t);
            }
            printf("%d\n",ans);
        }
    }
    
    展开全文
  • 今天发现在Integer中存在两个方法reverse和reverseBytes以前没有留意过且稍微需要点时间理解,遂写出分析思路。   注:文中为了方便讲述与理解,所有数字表示第x位而非下标。...即完成了整个二进制翻转
  • 例如一个二进制数是 0000 0000 0000 1100 我们的工作是将其反转为 0011 0000 0000 0000 我们当然可以从最低位按位与出每一位数, 然后从最高位开始排列下去. 但这里有一个更迅速的办法 假设我们要将 ...
  • 【LeetCode】Reverse Bits 翻转二进制

    千次阅读 2015-04-23 14:59:36
    至于翻转二进制,第一种思路是转成字符串之后,翻转字符串,再转成二进制,代码如下: public int reverseBits ( int n) { String valStr = Integer.toBinaryString(n); //System.out.println(valStr);...
  • 将输入转换成2进制字符串,再翻转并扩充到32位,再将此32位的二进制转为无符号整数 int 在内存中以二进制形式存储,占据32位。用一个 int 型整数 ans 来记录结果,采用移位操作,因为:1. 注意到移位操作比乘2、除...
  • c小白,求助大佬。![图片](https://img-ask.csdn.net/upload/201703/24/1490353309_605380.png)
  • 二进制翻转

    千次阅读 2019-05-31 08:20:52
    这个函数的返回值是value的二进制位模式从左到右翻转后的值。 如: 在32位机器上25这个值包含下列各位: 00000000000000000000000000011001 翻转后:(2550136832) 10011000000000000000000000000000 程序结果返回...
  • 主要介绍了C++二进制翻转,通过几个实例分析二进制翻转算法的实现技巧,需要的朋友可以参考下
  • BUPT 2018 计算机 ProblemA | 二进制和十进制相互转化算法
  • 掌握输出二进制码的算法 掌握二进制转换十进制的算法 unsigned int reverse_bit(unsigned int value) { int arr[40] = { 0 }; unsigned int num = 0; printf("... i++)//翻转二进制之后的二进制...
  • 问题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; ...

空空如也

空空如也

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

翻转二进制