精华内容
下载资源
问答
  • LeetCode29 两数相除

    2021-03-14 22:59:33
    29. 两数相除 给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。 返回被除数 dividend 除以除数 divisor 得到的商。 整数除法的结果应当截去(truncate)其小数部分...

    29. 两数相除

    给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
    返回被除数 dividend 除以除数 divisor 得到的商。
    整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2

    解题思路

    我只能说 要考虑类型溢出的题是真的噩梦 每次都要错几回

    没什么好说的思路 就是用除数每次 *2 一直到结果大于被除数 然后再用 (被除数-当前方法中的商) 作为被除数进行递归 结束判断是被除数小于除数
    重点在于:

    • 该递归方法只适用于两个正数 所以我们要将两个数化为正数
    • 一开始我根本没想到用long来存int 一直在想怎么让 int * -1 之后不溢出 (结果确实是没想出来)
    • 用到了long之后 又出了个问题 我用的是Math.abs() 来取绝对值 但tm以前没出现过这么大的数, 根本没想到它返回的就是int 然后错了

    最后: 吃一堑长一智 希望下次再碰到溢出的时候 不会再错了

    
        public static int divide(int dividend, int divisor) {
            int flag = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0) ? 1 : -1;
            if(divisor == 1){
                return dividend;
            }
            if(divisor == -1){
                if(dividend>Integer.MIN_VALUE) return -dividend;
                return Integer.MAX_VALUE;
            }
    
    
            long a = dividend>0?dividend:dividend*-1L;
            long b = divisor>0?divisor:divisor*-1L;
    
    
    
            return flag*getQuotient(a,b);
        }
    
        public static int getQuotient(long dividend,long divisor){
            if (dividend < divisor) {
                return 0;
            }
            int quotient = 1;
            while (divisor * quotient * 2 < dividend) {
                quotient *= 2;
            }
    
            return quotient + getQuotient(dividend-quotient*divisor,divisor);
    
        }
    
    展开全文
  • 29.两数相除

    2020-02-06 20:30:34
    这道题是要求数相除的结果是什么,但是不能用乘法,除法,mod 那我们思考一下结果的含义是什么,声明一个变量res来代表结果,res就是被除数里包含的除数的个数。这里假设被除数num1,除数为num2。 假设num1=20...

    感觉比较麻烦,想着想着就容易思绪打结,容易懵。。

    这道题是要求两个数相除的结果是什么,但是不能用乘法,除法,mod

    那我们思考一下结果的含义是什么,声明一个变量res来代表结果,res就是被除数里包含的除数的个数。这里假设被除数num1,除数为num2。

    假设num1=20,num2=3。1个num2=3, 2个num2=6,  4个num3=12,   8个num3=24,我们可以知道4<res<8,  最初的时候res为1,每次num2左移一位,res也跟着左移一位,因为num2变为原来的两倍,那么个数也要是原来的两倍才能达成。直到num2*2 > num1,说明此时的num2已经比num1的一半要大了,就不能在翻倍的扩大。这个时候num1减去res个num2剩下的值再拿来和最初的num2做递归,得到的个数加上res就是结果。这道题确实不是很好理解,说也有点说不清楚的感觉。。。

    递归部分的代码如下:

     

    然后这道题还有考虑边界的问题,是否达到了最大值或者最下值,这个也有点麻烦,代码如下:

    展开全文
  • 题29、两数相除

    2020-02-18 19:28:40
    暴力循环,判断当前剩余的部分能不能进行减一操作(假定是两个正数相除),能就继续,不能就结束并返回结果。 难点在于对什么时候停止循环进行判断,因为有符号不同这种情况。 最后我的解决办法就是依旧判断是否的...

    一、题目1

    在这里插入图片描述

    二、思路

    思路一:

    暴力循环,判断当前剩余的部分能不能进行减一操作(假定是两个正数相除),能就继续,不能就结束并返回结果。

    难点在于对什么时候停止循环进行判断,因为有符号不同这种情况。
    最后我的解决办法就是依旧判断是否的大于(假定正数除以负数),这样就多循环了两次,最后在结果中减去就ok了,然后最后提交超时,据我判断是倒在了-231这个边界值上面了,可以输出结果,但是,超时。

    思路二:

    这个思路主要的依据就是对任何一个整数n有:n=2n×a+2n-1×a+……+21×a+20×a

    然后就通过移位运算,最后得到结果。

    补充:

    对于符号的解决方法:我下面的代码中思路一是根据不同的符号进行判断,然后进行相应的方法。
    思路二的办法是将其均转化为正数进行计算。

    然后提交看了大佬的代码之后发现,转化为负数计算更加的方便,因为正数转负数不会越界,负数转正数存在越界的情况。

    三、代码

    public class T0029 {
    
        public T0029() {
    
            System.out.println( divide( -2147483647, 2 ) +" \t" + (-2147483647/2));
            System.out.println( divide( -2147483647, -2 ) +" \t" + (-2147483647/-2));
            System.out.println( divide( 2147483647, 2 ) +" \t" + (2147483647/2));
    
    
            System.out.println( divide( 2147483647, 1 ) +" \t" + (2147483647/1));
            System.out.println( divide( -2147483648, 1 ) +" \t" + (-2147483648/1));
            System.out.println( divide( 2147483647, -1 ) +" \t" + (2147483647/-1));
            System.out.println( divide( -2147483648, -1 ) +" \t" + (-2147483648/-1));
    
    
            for ( int i = 0; i < 10; i++ ){
                int a = (int)(Math.random()*1000);
                int b = (int)(Math.random()*100);
                System.out.println( divide( a, b ) == (a/b) );
            }
    
            for ( int i = 0; i < 10; i++ ){
                int a = (int)(Math.random()*1000);
                int b = (int)(Math.random()*100);
                System.out.println( divide( -a, b ) == (-a/b) );
            }
    
            for ( int i = 0; i < 10; i++ ){
                int a = (int)(Math.random()*1000);
                int b = (int)(Math.random()*100);
                System.out.println( divide( a, -b ) == (a/-b) );
            }
    
            for ( int i = 0; i < 10; i++ ){
                int a = (int)(Math.random()*1000);
                int b = (int)(Math.random()*100);
                System.out.println( divide( -a, -b ) == (-a/-b) );
            }
    
        }
    
        public int divide(int dividend, int divisor) {
    
            //判断是否是被除数为0,被除数除数均为最小值,除数为最小值
            //并对相应的情况进行处理
            if ( dividend == 0 || divisor==Integer.MIN_VALUE){
                return dividend==Integer.MIN_VALUE?1:0;
            }
    
            int a = 0;                      //被除数的绝对值
            int b = Math.abs(divisor);      //除数的绝对值
            boolean special = false;        //被除数是否是最小值
    
            int result = 0;                 //商
            int tmp = b;                    //暂时存储移位的结果
            int stape = 1;                  //暂时存储当前移位的值
    
            //判断被除数是否是最小值,并取其绝对值
            if ( dividend != Integer.MIN_VALUE ){
                a = Math.abs(dividend);
            }else {
                a = Math.abs(dividend+1);
                special = true;
            }
    
            //当被除数小于除数时循环结束
            while ( a >= b ){
    
                //判断此次位移结果是否会越界
                //不越界就进行位移,可能会越界就进行加减和初始化操作
                if ( tmp < Integer.MAX_VALUE >> 2 ){
    
                    //当位移结果小于被除数时,继续进行位移操作
                    //当大于时,就用被除数减去位移结果,并将stape的值加在result上
                    //同时将结果tmp、stape再次初始化
                    if ( tmp<<2 < a ){
                        tmp = tmp<<2;
                        stape = stape<<2;
                    }else {
                        a = a - tmp;
                        tmp = b;
                        result +=stape;
                        stape = 1;
                    }
                }else{
                    a = a - tmp;
                    tmp = b;
                    result +=stape;
                    stape = 1;
                }
            }
    
            //将result的符号修正
            if ( (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
                result = -result;
    
            //若被除数是最小值,将上面减去的1重新加回来,并进行计算
            if ( special && a+1==b ){
    
                //判断计算结果是否会越界
                if (result== Integer.MAX_VALUE)
                    return Integer.MAX_VALUE;
                else
                    result = result-1;
            }
    
            return result;
        }
    
    
        public int divide1(int dividend, int divisor) {
    
            if ( dividend == 0 ){
                return 0;
            }
            int result = 0;
            int tmp = divisor;
            int stape = 1;
    
            if ( dividend>0&&divisor>0 ){
                while ( dividend >= divisor ){
    
                    if ( tmp < Integer.MAX_VALUE >> 2 ){
                        if ( tmp<<2 < dividend ){
                            tmp = tmp<<2;
                            stape = stape<<2;
                        }else {
                            dividend = dividend - tmp;
                            tmp = divisor;
                            result +=stape;
                            stape = 1;
                        }
                    }else{
                        dividend = dividend - tmp;
                        tmp = divisor;
                        result +=stape;
                        stape = 1;
                    }
    
                }
            }else if ( dividend>0&&divisor<0 ){
                while ( dividend >= divisor ){
    
                    if ( tmp < Integer.MIN_VALUE >> 2 ){
                        if ( tmp<<2 < dividend ){
                            tmp = tmp<<2;
                            stape = stape<<2;
                        }else {
                            dividend = dividend + tmp;
                            tmp = divisor;
                            result -=stape;
                            stape = 1;
                        }
                    }else{
                        dividend = dividend + tmp;
                        tmp = divisor;
                        result -=stape;
                        stape = 1;
                    }
    
                }
    
                result += 2;
    
            }else if ( dividend<0&&divisor>0 ){
                while ( dividend <= divisor ){
    
                    if ( tmp < Integer.MIN_VALUE >> 2 ){
                        if ( tmp<<2 < dividend ){
                            tmp = tmp<<2;
                            stape = stape<<2;
                        }else {
                            dividend = dividend + tmp;
                            tmp = divisor;
                            result -=stape;
                            stape = 1;
                        }
                    }else{
                        dividend = dividend + tmp;
                        tmp = divisor;
                        result -=stape;
                        stape = 1;
                    }
    
                }
    
                result += 2;
    
            }else {
                while ( dividend <= divisor ){
    
                    if ( result == Integer.MAX_VALUE )
                        return Integer.MAX_VALUE;
    
                    if ( tmp < Integer.MIN_VALUE >> 2 ){
                        if ( tmp<<2 < dividend ){
                            tmp = tmp<<2;
                            stape = stape<<2;
                        }else {
                            dividend = dividend - tmp;
                            tmp = divisor;
                            result +=stape;
                            stape = 1;
                        }
                    }else{
                        dividend = dividend - tmp;
                        tmp = divisor;
                        result +=stape;
                        stape = 1;
                    }
    
                }
            }
    
            return result;
        }
    
        public static void main(String[] args) {
    
            T0029 t0029 = new T0029();
        }
    }
    

    1. 来源:力扣(LeetCode)
      链接:https://leetcode-cn.com/problems/divide-two-integers
      著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 ↩︎

    展开全文
  • 位运算前言简介371 两整数之和29 两数相除191. 位1的个数268 缺失数字136 只出现一次的数字137 只出现一次的数字 II260 只出现一次的数字 III338 比特位计数187 重复的DNA序列总结参考 前言 对0和1的操作计算机最...

    前言

    对0和1的操作是计算机最底层的操作,所有的程序不管用什么语言写的,都要转化成机器能够读懂的语言也就是二进制进行基本的运算,而这些基本的运算就是我们今天要讲到的位运算。因为硬件的支持,计算机在进行二进制计算的时候要比普通的十进制计算快的多,把普通的运算用位运算的方法实现能够极大提高程序性能,是一个重要的技能。

    简介

    在计算机中有超过七种位运算操作,在这里就以Java为例来讲解Java中需要用到的七种位运算符。

    符号 描述 规则 举例
    & 按位与 左右两侧同时为1得到1,否则为0 1&1=1
    1&0=0
    | 按位或 左右两侧只要一个是1就返回1,都是0才返回0 1|0=1
    0|0=0
    ^ 按位异或 左右两侧相同时为0,不同为1 11=0<br>00=0
    1^0=1
    ~ 按位取反 1变成0,0变成1 1=0<br>0=1
    << 有符号左移 保持最高位的符号,其他的位向左移动,右侧用0补齐 1<<2=4
    >> 有符号右移 保持最高位符号,其他位向右移动,除最高位其他用0补齐 5>>1=2
    -10>>1=-5
    >>> 无符号右移 所有位都向左移动,高位用0补齐 5>>>1=2
    -10>>>1=2147483643

    既然说到了位运算就不得不提一下在Java中int类型数字的表示,Java的int一共是32位,其中第32位符号标志位,如果是0就代表是正数,1代表是负数,比如1的表示方法是0000 0000 0000 0000 0000 0000 0000 0001,最大只能是前31位都置1的结果,也就是23112^{31}-1;对于负数的表示需要注意,并不是直接把对应的正数最高位0变成1,而是全部位取反然后加一,这样做的目的是为了让两个二进制数字直接相加的和为0,比如-1的表示方法是1111 1111 1111 1111 1111 1111 1111 1111,这样两个数字二进制相加得到的最终结果是0(最高位溢出舍弃掉)。负数的最小值是2312^{31},绝对值比正数最大值大一位,因为这个负数比较特殊,二进制表示为1000 0000 0000 0000 0000 0000 0000 0000,在取反加一之后还是它本身。

    这里顺带介绍一下位操作的小技巧,其中的原理可以自己揣摩

    序号 公式 解释(n0开始)
    1 num |= 1<<n numn位设置为1
    2 num &= ~(1<<n) numn位设置为0
    3 num ^= 1<<n numn位取反
    4 num & (1<<n) == (1<<n) 检查numn位是否为1
    5 num = num & (num-1) num最低位的10
    6 num & -num 获得num最低位的1
    7 num &= ~((1<<n+1)-1) numn位右侧置0
    8 num &= (1<<n)-1 numn位左侧置0

    更多位操作相关技巧可以看这里这里


    这里捎带着说一下浮点类型float在Java中的表示,如果已经比较清楚的同学可以直接跳过这个部分。浮点数总共4个字节,表示可以用下面的公式:

    (1)s×m×2e127 (-1)^s \times m \times 2^{e-127}

    其中

    • s,第31位,如果是1代表是负数,0代表正数
    • e,第30~23位,是指数位,表示一个无符号的整数,最大是255
    • m,第22~0位,尾数,包含了隐藏的1,表示小数位,需要去掉后面的无效的0

    比如在浮点数0.15625在二进制中的表示方法是0011 1110 0010 0000 0000 0000 0000 0000(使用Java代码Integer.toBinaryString(Float.floatToIntBits(0.15625F))可以得到浮点数的二进制表示,但是省去了最高位的0),其中

    • 第31位0,表示正数
    • 第30~23位,011 1110 0指数位,十进制是124,减去127之后得到-3
    • 第22~0位,010 0000 0000 0000 0000 0000尾数数,舍去小数后面的0之后得到01,加上默认1后得到1.01(二进制表示的小数)
    • 综上根据公式得到0.15625的二进制公式为(1)0×(1.01)×23=0.00101(-1)^0\times(1.01)\times2^{-3}=0.00101,然后把二进制转成十进制就变成了23+25=0.125+0.03125=0.156252^{-3}+2^{-5}=0.125+0.03125=0.15625

    double类型和float的计算方法一样,只不过double的指数位有11位,尾数位52位,计算指数的时候需要减去1023。相比于float,double的精度要高很多,如果不在意空间消耗的情况下,最好用double。


    现在基本的计算机的操作我们知道了,数字的二进制表示我们也清楚了,那么如何通过二进制的位运算来完成十进制数字的计算呢?下面来一一揭晓。

    371 两整数之和

    Leetcode第371题两整数之和

    不使用运算符+-​​​​​​​,计算两整数​​​​​ab​​​​​​之和。

    示例1:

    输入: a = 1, b = 2
    输出: 3

    示例2:

    输入: a = -2, b = 3
    输出: 1

    这道题在leetcode的美国网站上面有1900多个dislike,看来大家对这个题目意见很大,不过就趁这个机会回顾一下计算机是怎样进行加法操作的。

    回顾一下我们小学就开始学习的十进制的加法,比如15+7,最低位5+7得到12,对10取模得到2,进位为1,再高位相加1+0再加上进位1就得到高位结果2,组合起来就是22。这里面涉及到了两个数字,一个是相加得到的低位,也就是5+7得到的结果2,第二个是进位1。在二进制的计算中就是要通过位操作来得到结果的低位和进位,对于不同的情况,用表格来表示一下,两个数字分别为ab

    a b 低位 进位
    0 0 0 0
    1 0 1 0
    0 1 1 0
    1 1 0 1

    从上面的表格就可以发现,低位 = a^b进位 = a & b。这样的计算可能要持续多次,回想一下在十进制的计算中,如果进位一直大于0,就得往后面进行计算,在这里也是一样,只要进位不是0,我们就得一直重复计算低位和进位的操作(需要在下一次计算之前要把进位向左移动一位,这样进位才能和更高位进行运算)。这个时候的ab就是刚才计算的低位和进位,用简单的加法迭代的代码表示:

    public int getSum(int a, int b) {
        if (a==0) return b;
        if (b==0) return a;
        int lower;
        int carrier;
        while (true) {
            lower = a^b;    // 计算低位
            carrier = a&b;  // 计算进位
            if (carrier==0) break;
            a = lower;
            b = carrier<<1;
        }
        return lower;
    }
    

    29 两数相除

    这是leetcode第19题两数相除

    给定两个整数,被除数dividend和除数divisor。将两数相除,要求不使用乘法、除法和mod运算符。

    返回被除数dividend除以除数divisor得到的商。

    示例1:

    输入: dividend = 10, divisor = 3
    输出: 3

    示例2:

    输入: dividend = 7, divisor = -3
    输出: -2

    说明:

    • 被除数和除数均为 32 位有符号整数。
    • 除数不为 0。
    • 假设我们的环境只能存储 32 位有符号整数,其数值范围是[231,2311][−2^{31}, 2^{31} − 1]。本题中,如果除法结果溢出,则返回23112^{31} − 1

    这道题其实可以很容易联想到我们经常用到的十进制的除法,这里有一个例子来说明如何把十进制除法的思想套用在二进制上面。

    binary division

    图片是用33除以6,对应二进制100001除以110,有三步:

    1. 将被除数从110开始向左移位右侧补0,直到找到最大的比100001小的数字11000(图中右侧的0已经被省略掉了),这个时候向左移动了两位也就是乘以100(二进制),余数是1000
    2. 再将110向左移动到最大的比1000小数字,这个时候就是本身,相当于乘以1(向左移动了0位),余数是11
    3. 因为余数已经比被除数110要小了,这个时候可以直接停止运算,将上面两个步骤计算得到的乘数1001)加起来就是我们最后的结果了(101)。

    这里我们就用java代码来实现一下这个逻辑:

    public int divide(int dividendInt, int divisorInt) {
        int shiftedDivisor;                   // 移位后的除数
        int quotient = 0;                     // 记录除法得到的商
        int remainder = dividendInt;
    
        while (remainder>=divisorInt) {
            int tempQuotient = 1;             // 临时的商
            dividendInt = remainder;          // 处理上一轮的余数
            shiftedDivisor = divisorInt;      // 重置被除数
            while (dividendInt>=shiftedDivisor) {
                shiftedDivisor <<=1;
                tempQuotient <<= 1;
            }
            quotient += tempQuotient >> 1;    // 累加计算得到的商
            remainder = dividendInt - (shiftedDivisor >> 1); // 位移优先级比减号低,要用括号
        }
        return quotient;
    }
    

    通过循环的方法得到了我们要的除法的实现逻辑,但是这个方法只是对除数和被除数都是正数才起作用,比如除数是-100被除数是10或者-10的时候,返回的结果是0!对于-100除以-10这个例子,在比较余数和移位的除数的大小的时候,如果都是正数,余数比除数小的时候停止循环是正常的,但是在都是负数的时候,这样做就有问题了,余数比除数大,商才是0,所以上面两个循环的终止条件的不等号方向换一下就可以了。

    public int divide(int dividendInt, int divisorInt) {
        int shiftedDivisor;
        int quotient = 0;
        int remainder = dividendInt;
    
        while (remainder<=divisorInt) {           // 注意 变成了小于等于
            int tempQuotient = 1;
            dividendInt = remainder;
            shiftedDivisor = divisorInt;
            while (dividendInt<=shiftedDivisor) {  // 注意 变成了小于等于
                shiftedDivisor <<=1;
                tempQuotient <<= 1;
            }
            quotient += tempQuotient >> 1;
            remainder = dividendInt - (shiftedDivisor >> 1);
        }
        return quotient;
    }
    

    现在我们都是正数和都是负数的情况都有了,一个正数一个负数咋办呢?那就把符号变一下,变成一样的,最后在返回结果的时候变回来。这里题目善意的提醒了一下要考虑边界问题,在考虑转换符号的时候需要考虑到-2147483648这个值的特殊性,也就是负数变正数要小心,但是正数变成负数可以随意,那就不如直接负数运算得了(参考这篇文章)。在累加每一次除法得到的商的时候,也是使用负数-1的移位来避免溢出问题(比如-2147483648除以1带来的溢出问题)。

    在对除数进行移位的时候,还需要注意一下移位之后除数不能溢出,能够使用的最好方法就是在移位之前判断一下除数是否是小于最小数字的一半(如果是用正数移位的话,就应该是判断是否是大于最大数字的一半),如果小于,下一次移位一定就会溢出,这个时候就只能直接终止循环。

    在判断结果的符号的时候用一下位运算的小技巧,在上面讲到异或操作的时候,如果是相同的就返回0,否则是1,所以对两个数字最高位进行异或操作,如果是0就代表结果是正号,反之就是负号。除此之外还有一个极端情况,当被除数取最小值-2147483648并且除数取-1的时候,得到的结果是2147483648会溢出,因为只有这样的一个特例,可以直接排除,对于剩下的其他的数字不管怎样都不会溢出,整理之后的代码如下:

    public int divide(int dividendInt, int divisorInt) {
        if (dividendInt == Integer.MIN_VALUE && divisorInt == -1) {
            return Integer.MAX_VALUE;         // 对于极端情况,直接排除,返回int最大值
        }
        boolean negSig =
                ((dividendInt ^ divisorInt) & Integer.MIN_VALUE) == Integer.MIN_VALUE;  // 判断结果是否是负数
    
        dividendInt = dividendInt > 0 ? -dividendInt : dividendInt;                     // 被除数取负值
        divisorInt = divisorInt > 0 ? -divisorInt : divisorInt;                         // 除数取负值
    
        int shiftedDivisor;                   // 移位后的除数
        int quotient = 0;                     // 记录除法得到的商
        int remainder = dividendInt;
        int minShiftDivisor = Integer.MIN_VALUE >> 1; // 防止溢出,大于这个值之后不能再向左移位了
    
        while (remainder<=divisorInt) {
            int tempQuotient = -1;             // 临时的商,全部用负数处理
            dividendInt = remainder;           // 处理上一轮的余数
            shiftedDivisor = divisorInt;       // 重置被除数
            while (dividendInt<=(shiftedDivisor<<1)          // 比被除数小才进行接下来的计算
                    && shiftedDivisor >= minShiftDivisor) {  // 判断是否移位后会溢出
                shiftedDivisor <<=1;
                tempQuotient <<= 1;
            }
            quotient += tempQuotient;                        // 累加计算得到的商
            remainder = dividendInt - shiftedDivisor;        // 得到余数,下一轮作为新的被除数
        }
    
        return negSig?quotient:-quotient;     // 如果是负数就直接返回结果,如果不是就变换成正数
    }
    

    191. 位1的个数

    leetcode第191题位1的个数

    编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为1的个数(也被称为汉明重量)。

    示例1:

    输入:00000000000000000000000000001011
    输出:3
    解释:输入的二进制串00000000000000000000000000001011中,共有三位为’1’。

    示例2:

    输入:00000000000000000000000010000000
    输出:1
    解释:输入的二进制串00000000000000000000000010000000中,共有一位为 ‘1’。

    这道题任何人最简单暴力的做法就是直接移位,在Java里面直接用无符号的右移,每次判断最低位是不是1,把判断为1的所有的次数记录起来就可以了。

    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += n&1;  // 累加1
            n>>>=1;        // 循环右移1位
        }
        return count;
    }
    

    但是这道题有一个更加有意思的解法,首先对于一个二进制数字比如10100,在减一操作之后得到10011,比较这两个数字,发现原数字最低位的1的右边的数字没有变,而右边的0都变成了1,而这个1变成了0,如果对原来的数字和减一的数字进行按位与,就会把最低位的1置零。

    所以就有了一个神奇的想法,如果我们想把数字a最低位的1变成0而不改变其他位,直接通过a&(a-1)就可以得到了,而把所有的1都变成了0的次数不就是位1的个数了吗?

    比如对于数字101,在经过a&(a-1) = 101&100 = 100,再操作一次就是100&011 = 0,一共两次操作,最后的结果就变成了0

    简单代码如下:

    public int hammingWeight(int n) {
        int count = 0;    // 统计置0的次数
        while (n!=0) {
            count ++;
            n = n&(n-1);  // 最低位的1置0
        }
        return count;
    }
    

    看起来上面两个算法都可以达到我们想要的目的,但是不知道效率怎么样,那就来测试比较一下(添加的java的内置计算1个数的方法)

    private void test() {
        int t = 10000000;                        // 比较一千万次
        long s = System.currentTimeMillis();
        for (int i = 0; i < t; i++) {
            hammingWeight1(-3);
        }
        System.out.println("Java builtin:\t" + (System.currentTimeMillis()-s));
        s = System.currentTimeMillis();
        for (int i = 0; i < t; i++) {
            hammingWeight2(-3);
        }
        System.out.println("最低位1置0:   \t" + (System.currentTimeMillis()-s));
        s = System.currentTimeMillis();
        for (int i = 0; i < t; i++) {
            hammingWeight3(-3);
        }
        System.out.println("向右移位比较:\t" + (System.currentTimeMillis()-s));
    }
    
    // java内置方法
    public int hammingWeight1(int n) {
        return Integer.bitCount(n);
    }
    
    // 最低位1置0
    public int hammingWeight2(int n) {
        int count = 0;
        while (n!=0) {
            count ++;
            n = n&(n-1);
        }
        return count;
    }
    
    // 向右移位比较
    public int hammingWeight3(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += n&1;  // 累加1
            n>>>=1;        // 循环右移1位
        }
        return count;
    }
    

    输出的结果如下:

    Java builtin:   10
    最低位1置0:     150
    向右移位比较:    10
    

    虽然上面只是一次测试的结果(每次运行测试的时候结果都不一样),但是可以看出最低位置0这个方法效率要比普通的移位操作或者内置的方法慢一个数量级,猜测原因应该是n=n&(n-1)这个操作耗时比较高(n=n&(n-1)其实是两步,第一步int a = n-1,第二步n=n&a),而n&1或者n>>>=1这两个操作都要快很多。

    回到测试,多测几次发现java内置的方法有的时候要比向右移位快很多,这就有意思了,得看看它到底是怎么实现的:

    public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }
    

    看完之后一句卧槽涌上心头,这写的是什么玩意儿?!这是什么神仙算法!那就来仔细看看这个算法,对每一步进行分解,假设我们的输入是-1

    public static int bitCount(int i) {                  // i = 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11  -1的二进制
        // HD, Figure 5-2                                //     01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01  
        i = i - ((i >>> 1) & 0x55555555);                // i = 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10  (1)每2位的计算
                                                         //     00 11 00 11 00 11 00 11 00 11 00 11 00 11 00 11  
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); // i = 0100 0100 0100 0100 0100 0100 0100 0100          (2)每4位求和
                                                         //     0000 1111 0000 1111 0000 1111 0000 1111
        i = (i + (i >>> 4)) & 0x0f0f0f0f;                // i = 00001000 00001000 00001000 00001000          (3)每8位求和
    
        i = i + (i >>> 8);                               // i = 0000100000010000 0001000000010000            (4)每16位求和
    
        i = i + (i >>> 16);                              // i = 00001000000100000001100000100000             (5)每32位求和
    
        return i & 0x3f;                                 // i = 00000000000000000000000000 100000            (6)取最低的6位
    }
    

    这个过程一共有6步,主要思想就是分治法,计算每2、4、8、16、32位中1的个数:

    1. 第一步也是最重要的一步,统计每2位里面的1的个数,比如二进制11有两个1应该变成统计结果1011-((11>>>1)&01) = 10),10或者01应该变成0110-((10>>>1)&01) = 0101-((01>>>1)&01) = 01
    2. 统计每4位里面的1的个数,也就是把上面计算得到的两位1的个数和相加,比如01 00,通过移位并且和掩码0011按位与,变成00000001然后求和得到0001
    3. 统计每8位二进制里面1的个数,这一步跟上面又不一样了,不是先用掩码再相加,而是先相加再用掩码,主要不同地方是在上一步两个二位的二进制数字相加可能会溢出,使用掩码之后就会得到错误的结果,比如10 10,相加得到01 00然后用00 11按位与得到00 00不是我们想要的结果。当计算8位的个数的时候就不会溢出,因为4位里面1的个数最多是4个,也就是0100,两个相加最大是1000,不会进位到第二个4位,使用掩码能够得到正确的结果,并且可以清除多余的1
    4. 统计每16位二进制里面1的个数,这个时候直接移位相加并没有用掩码,原因很简单,在上一步的每8位里面的的结果的是保存在最后4位里面,并且一定是准确的,直接相加肯定不会溢出8位,结果也一定保存在最右边的8位里面,至于16位里面的左边的8位是什么值我们根本就不关心,所以没有必要用掩码,也不会影响后面的计算
    5. 这一步得到32位的和,直接移位相加,因为左右16位的1的个数一定保存在他们各自的右侧8位,相加的结果也不会溢出,一定还在最右的8位里面,左边的24位是什么也没有影响
    6. 结果一定在最后的6位里面,因为一共最多只有32个1,只需要6位来保存这个值。

    这样就通过一个精细的二进制的运算利用分治法得到了最后1的个数,不得不感叹这样的做法实在是太妙了!

    Java中还有很多精妙的整型数字的位操作方法比如下面的几种,虽然很想介绍一下,不过因为篇幅原因就跳过,因为后面还有更加重要的内容

    • highestOneBit
    • lowestOneBit
    • numberOfLeadingZeros
    • numberOfTrailingZeros
    • reverse
    • rotateLeft
    • rotateRight

    268 缺失数字

    leetcode第268题缺失数字

    给定一个包含0, 1, 2, ..., nn个数的序列,找出0 .. n中没有出现在序列中的那个数。

    示例1:

    输入: [3,0,1]
    输出: 2

    这道题可以用哈希表或者求和的方法,都是不错的方法,不过既然这篇文章是关于位运算的,就用经典的位运算吧。

    对于数字的位运算,按位异或有一个很重要的性质,对于数字ab有:

    a^a=0

    a^0=a

    a^b^a=b

    以此类推可以发现如果对于一个数组里面的每一个元素都进行按位异或,里面的出现频率是偶数的元素都会变成0,如果数组里面每个元素的出现频率都是偶数次,那么整个数组的按位异或的结果就是0,如果只有一个元素出现了奇数次,按位异或的结果就是这个元素。

    回到这道题,数组中所有的数字出现的次数是1,没有出现的数字次数是0,明显不能直接按位异或,那我们就再这个数组后面添加一个0..n的数组,包含所有的元素,这样两个数组合起来原来出现的数字的出现次数是2,而原来没有出现的数字的出现次数是1,就可以用按位异或了。

    不过这里并不需要显性的添加数组,而是在循环内部再进行异或操作,代码如下:

    public int missingNumber(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= i^nums[i];           // 循环内部尽量按位异或虚拟的新增数组
        }
        return xor^nums.length;         // 补齐循环中漏掉的最后一个数字n
    }
    

    136 只出现一次的数字

    leetcode第136题只出现一次的数字

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    说明

    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

    示例 1:

    输入: [2,2,1]
    输出: 1

    根据上面一题的按位异或的思路,这道题可以闭着眼睛写出结果:

    public int singleNumber(int[] nums) {
        int num = 0;
        for (int i : nums) {
            num ^= i;
        }
        return num;
    }
    

    137 只出现一次的数字 II

    这是leetcode第137题只出现一次的数字 II

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

    说明:

    你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

    示例 1:

    输入: [2,2,3,2]
    输出: 3

    这道题和上面的那一道题看起来似乎是很相似的,不同之处仅仅是在于原来是出现2次,现在是变成了3次,原来有异或的运算操作,可以让a^a=0,如果有一个操作符号使得a?a?a=0,那这个问题就迎刃而解了。好像并不存在这样的运算符,那就想想其他的方法。

    首先看看异或运算符的特点,1^1=00^1=11^0=10^0=0,联想到加法运算,01+01=10取低位为0,所以其实就是运算符左右相加去掉进位(相当于对2取模)。如果想让三个1相加得到0,那就用十进制里面的相加然后对3取模就可以了的。

    这样对这个数组里面的每个数字二进制位的每一位相加并且最后对3取模,得到的就是只出现一次的数字的每一个二进制位的结果。初步想法的代码如下:

    public int singleNumber(int[] nums) {
        int bit;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            bit = 0;
            for (int num : nums) {        // 计算第i位的1的个数
                bit += (num>>i)&1;
            }
            res |= (bit%3)<<i;        // 根据1的个数取模得到结果
        }
        return res;
    }
    

    这其实也是一个比较通用的解法,这里出现的次数是3次,如果换成了4次、5次也能用这个方法解决。看了很多其他人的解法,还有一个更加精妙的解法,参考这里

    在上面的解法里面,我们用一个bit来保存所有的数字的某一位的和,每个元素都是int类型的,但是这道题的最多的重复次数是3,而且我们最后需要的结果并不是这个和,而是和对3取模,所以如果能够在计算的过程中不停的取模,就能控制每一位的和小于3,最多2位的二进制数字就可以了,并不需要32位的int来保存。虽然在java里面没有一个只有2位bit的二进制数字,但是可以用两个1位的二进制数字来表示,这样整个数组用两个int类型的数字表示就可以了。上面解法的另外一个问题是整个数组被遍历了32遍,因为每计算一位都要遍历一遍,但是如果用两个int来代表的话,用适当的位操作,可以把遍历次数降低到一次!

    先用lowerhigher代表这个二进制数字的低位和高位,每次遇到一个二进制数字的数字的时候的变化可以用下图表示(因为遇到3取模得到0,所以不可能有lower=1 higher=1这种状态,只能是中间存在的一种过渡状态)。

    num higher(old) lower(old) higher(过渡) lower(过渡) mask(掩码) higher(new) lower(new)
    0 0 0 0 0 1 0 0
    0 0 1 0 1 1 0 1
    0 1 0 1 0 1 1 0
    1 0 0 0 1 1 0 1
    1 0 1 1 0 1 1 0
    1 1 0 1 1 0 0 0

    是不是感觉有点懵逼,得到了这样的一个表格又要怎么把它变成公式呢?

    首先看一下从老的状态到过渡状态,完全就是一个二进制的加法,低位的数值根据lowernum可以得到的过渡状态是lower=lower^num;而高位的数值需要得到低位的进位,也就是lower&num,然后加上原来的高位就是higher^(lower&num),通过这两部就可以轻松计算出过渡状态的高位和低位。

    过渡状态可以出现higher=1 lower=1的状态,如果是出现是4次的话,这道题就直接解决了,不用任何额外的操作就可以得到最后的新状态,但是我们这里要求的是3次,也就是当higher=1 lower=1的时候需要把两位同时置零,为其他的状态时就保持不变。这个时候就要用到掩码,先计算出掩码,再通过掩码把过渡状态修正成最终的状态。掩码时根据过渡状态的高低位决定的,如果过渡状态的高低位组成的数字达到了我们想要的阈值(这道题里面是3),掩码变成0,高低位同时进行&操作置零;没有达到的时候就是1,使用&操作相当于维持原来的值。可以看到这道题当higher=1 lower=1时掩码mask=0,其他时候mask=1,很熟悉的操作,这不就是mask=~(higher&lower)吗!这道题已经水落石出了!

    最后的新状态直接用过渡状态和掩码按位与,higher=higher&masklower=lower&mask就到了新的值。

    遍历完了整个数组之后,出现了三次的数字计算得到的higherlower一定是0,出现了一次的数字的higher一定也是0,而lower低位就是表示的出现一次的数字的二进制位的值,所以最后得到的lower就是需要的返回结果。

    public int singleNumber(int[] nums) {
        int higher = 0, lower = 0, mask = 0;
        for (int num : nums) {
            higher = higher^(lower&num);
            lower  = num^lower;
            mask = ~(higher&lower);       // 计算掩码
            higher &=mask;
            lower &= mask;
        }
        return lower;
    }
    

    上面的求解过程简单点来将就是先用加法得到过渡状态,再用掩码计算出最终的新状态,对于任何出现了k次的数组中找到只出现了一次的数字的题目都能用,这里只有两位(一个高位,一个低位)。如果k=5,那么2位就不够了,需要3位数字来表示s1s2s3,而掩码的计算就变成了mask = ~(s3&~s2&s1)(当过渡状态为101的时候掩码为0)。

    如果把上面的掩码的计算变成了mask=~(higher&~lower),这段代码就可以直接放到只出现一次的数字这道题里面。

    除了使用过渡状态,还可以使用卡诺图来直接解决新老状态转换的问题,具体的解题方法可以看这个帖子

    260 只出现一次的数字 III

    这是leetcode第260题只出现一次的数字 III

    给定一个整数数组nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

    示例 :

    输入: [1,2,1,3,2,5]
    输出: [3,5]

    注意:

    1. 结果输出的顺序并不重要,对于上面的例子,[5, 3]也是正确答案。
    2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

    这道题和上面的不同之处在于上面需要求解的元素的出现次数只是一次,得到最后一个元素就可以了,然而这道题需要求解两个出现一次的元素。比如这两个元素分别是ab,一次遍历经过按位异或之后得到的结果是a^b,从这个信息里面我们貌似什么结论都得不到。

    既然要得到两个数字,需要遍历两次,如果两次都全部遍历,我们想要的信息就会混在一起,唯一的方法就是把这个数组分成两个子数组,一个数组包含a,另一个包含b,这样分别遍历就能够得到想要的ab了。

    要想拆分这个数组,需要区分ab,由于ab一定是不同的,二进制表示的32位里面一定有1位是不同的,找到了这一位,然后把整个数组里面这一位为1的和为0数字分别列为两个子数组(同一个数字肯定会被划分到同一个子数组里面),分别异或就能够得到结果了。为了找到ab不同的二进制位,上面得到的a^b就能派上用场了,异或结果为1的肯定是两个数字不同的那一位,随便找一个就可以区分,这里我们直接为1的最低位。在文章的开头就有获取最低位的1的操作——num&(-num),可以直接使用,简化的代码如下:

    public int[] singleNumber(int[] nums) {
        if (nums == null || nums.length < 1) return null;
        int[] res = new int[2];
        int xor = 0;
        for (int num : nums) {   // 计算a^b
            xor = xor^num;
        }
        int bits = xor & (-xor); // 获取最低位1
    
        for (int num : nums) {   // 获取其中一个出现次数位1的数字a
            res[0] ^= (bits & num) == bits ? num : 0;
        }
        res[1] = res[0]^xor;     // 根据根据前面的数字得到另一个数字b
        return res;
    }
    

    338 比特位计数

    这是leetcode第338题比特位计数

    给定一个非负整数num。对于0 ≤ i ≤ num范围中的每个数字i,计算其二进制数中的1的数目并将它们作为数组返回。

    示例 1:

    输入: 2
    输出: [0,1,1]

    示例 2:

    输入: 5
    输出: [0,1,1,2,1,2]

    进阶:

    • 给出时间复杂度为**O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)**内用一趟扫描做到吗?
    • 要求算法的空间复杂度为O(n)

    看完这道题,看到最后的进阶部分,是不是感觉到很眼熟——要求线性时间内解决问题,空间复杂度位O(n)——这不就是动态规划吗!想想这道题的问题的特点,找找最优子结构。

    对于一个二进制数字n,如果想得到他的从左到右第n位中的1的个数,可以先得到它的从左到右第n-1位中的1的个数,然后根据第n位是否是1来决定是否要加1。要得到整个数字中的1的个数,就需要知道从左到右第31位(从1开始计数)中的1的个数,以及最低位是否是1。得到前者并不难,因为如果把整个数字向右移一位就是一个前面已经计算过的数字(动态规划从小到大开始计算),这就变成了最优子结构了,递推公式变成了res[i] = res[i>>1] + (i&1);,有了这个公式问题就解决了。

    比如如果想得到10也就是二进制10101的个数,可以先找到左边三个二进制数字1011的个数,加上最右侧的位0就可以了。

    public int[] countBits(int num) {
        int[] res = new int[num+1];      // 不需要初始化,默认为0
        for (int i = 0; i < res.length; i++) {
            res[i] = res[i>>1] + (i&1);
        }
        return res;
    }
    

    187 重复的DNA序列

    这是leetcode第187题重复的DNA序列

    所有 DNA 都由一系列缩写为 A,C,G 和 T 的核苷酸组成,例如:“ACGAATTCCG”。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。

    编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列(子串)。

    示例:

    输入:s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT”
    输出:[“AAAAACCCCC”, “CCCCCAAAAA”]

    看到了前面的那么多的明摆着用位操作的题目,再跳到这个题目感觉是不是有点蒙蔽,似乎跟位操作一点关系都没有。但是注意读题,里面有两个关键的限定条件——10个字母长的序列只有“ACGT”四个字符,看到这两个条件就联想到一个int数字有32位,所以一个int数字就能够正好代表这样的一个10个字符长的序列。

    在实现中我们用

    • 00代表A
    • 01代表C
    • 10代表G
    • 11代表T

    比如序列AAAAACCCCC就可以用00 00 00 00 00 01 01 01 01 01来表示,这只是从右到左的20位,更高位都是0省略掉了。

    一串DNA正好需要20位,高位直接用掩码去掉。每一个唯一的DNA串都能用一个唯一的int数字表示,用一个数组来表示每一串出现的次数,数组最大长度是1<<20

    public List<String> findRepeatedDnaSequences(String s) {
        if (s == null || s.length() <= 10) return new ArrayList<>();
        char[] chars = s.toCharArray();              // 转化成数组提高效率
        int[] freq = new int[1<<20];                 // 出现频率数组
        int num = 0;                                 // 计算过程中的int值
        int mask = (1<<20)-1;                        // 掩码,只保留最低的20位
        for (int i = 0; i < 10; i++) {               // 初始化第一个DNA串
            num <<= 2;
            if (chars[i] == 'C') {
                num |= 1;
            } else if (chars[i] == 'G') {
                num |= 2;
            } else if (chars[i] == 'T') {
                num |= 3;
            }
        }
        freq[num]++;
        List<Integer> repeated = new ArrayList<>();
        for (int i = 10; i < chars.length; i++) {    // 遍历所有的长度为10的DNA串
            num <<= 2;                               // 清楚最高的两位,也就是移除滑出的字符串
            if (chars[i] == 'C') {
                num |= 1;
            } else if (chars[i] == 'G') {
                num |= 2;
            } else if (chars[i] == 'T') {
                num |= 3;
            }
            num &= mask;                             // 掩码 保留最低的20位
            freq[num]++;                             // 统计出现频率
            if (freq[num] == 2) repeated.add(num);   // 只有出现次数是2的时候才计入,避免重复
        }
    
        List<String> res = new ArrayList<>(repeated.size());
        for (Integer integer : repeated) {           // 将int数字转化成DNA串
            char[] seq = new char[10];
            for (int i = 9; i >= 0; i--) {
                switch (integer&3) {
                    case 0:seq[i]='A';break;
                    case 1:seq[i]='C';break;
                    case 2:seq[i]='G';break;
                    case 3:seq[i]='T';break;
                }
                integer >>=2;
            }
            res.add(new String(seq));
        }
        return res;
    }
    

    总结

    这篇文章主要主要讲解了二进制位操作的几个基本的使用方法和小技巧,顺带提了一下浮点型数字的表示方法,希望能够增加对计算机底层的数据的理解。

    后面讲到了几个leetcode上面的比较经典的题目比如两数相除只出现一次的数字,都是使用位运算解决实际的问题,而重复的DNA序列是更高层次的通过位运算解决问题的案例。

    洋洋洒洒写了几千字,希望帮助大家加深对位运算的理解,并能够熟练运用在工作学习中。

    参考

    A summary: how to use bit manipulation to solve problems easily and efficiently
    Bit Manipulation 4% of LeetCode Problems
    Bit Twiddling Hacks
    Bitwise operators in Java
    9.1 Floating Point
    java浮点数的二进制格式分析
    How is a floating point number represented in Java?
    执行时间1ms,击败100%
    详细通俗的思路分析,多解法
    Detailed explanation and generalization of the bitwise operation method for single numbers
    Bitwise Hacks for Competitive Programming
    Bit Tricks for Competitive Programming

    更多内容请看我的个人博客

    展开全文
  • 先看个例子: int i=4;...除数iint类型,用3相除得到结果也int类型。就是0.然后赋值给num.此时只是0被转成了double。。所以还是0.0解决办法:int i=4;double num=3/(double)i; 输入结果就是0.75了...
  • 数据类型编程中最基础的知识,入门时很容易理解,但有时会因为编译器换算的问题,而得不到正确的答案。特别做硬件的,像我这样,既搞硬件又搞软件一心想走嵌入式之路的人,有时会遇到要计算晶振频率,如果结果...
  • 上篇回顾上篇的内容不...变量的定义格式是什么?标识符的组成规则是什么?类型转换分为哪些?学习目标运算符1.1. 算术运算符1.2. 赋值运算符1.3. 自增自减运算符1.4. 关系运算符1.5. 逻辑运算符1.6. 三元运算符键盘...
  • /*什么是辗转相除法呢? 比如求x,y的最大公约数, 先讨论(x%y)的余数b是否等于0, 如果, 则y为最大公约数; 否则将y的值赋给x, 把b的值赋给y然后再继续对b讨论, 一直循环下去直到b=0时, y值就是所求的最大公...
  •  辗转相除法就是用一个数模上另一个数(如a%b)的余数如果等于零,则b为两数最小公约数。若不为零则再用b模上余数c(如b%c),如果余数为零,则c为最小公约数。若余数不为零,继续按规律往后模...  128%48 商2余...
  • 言归正传,首先我们要知道面试官出求的最大公约数这个题目的目的是什么。知己知彼,才能百战不殆嘛。这个问题首先考察的是候选人的数学功底,就是看你知不知道一些求公约数的算法,比如...
  • 什么是辗转相除法?  辗转相除法(又名欧几里德算法),它主要用于求个正整数的最大公约数。已知的最古老的算法。  用辗转相除法求132和72的最大公约数的步骤:  132 / 72 = 1 ... 60  72 / 60 = 1 ... ...
  • 用“辗转相除法”将两数的最大公因数表成两数的线性组合 2019年8月22日星期四 本文接前文: ——《用现代数学方法解古题“物不知数”一、平凡的开端:表达带余除法的小技巧文中图片均来自网络 如果要做20除以6,...
  • 漫画算法:辗转相除是什么鬼?

    千次阅读 2017-03-21 15:16:33
    小灰的思路十分简单。他使用暴力枚举的方法,试图寻找到一个合适的整数 i,看看这个整数能否被两个整型参数numberA和numberB同时整除。...循环结束后,上一次寻找到的能够被两数整除的最大 i 值,就是两数的最大公约
  • 两数为a、b(b),用gcd(a,b)表示a,b的最大公约数,r=a mod b 为a除以b以后的余数,k为a除以b的商,即a÷b=k.......r。辗转相除法即要证明gcd(a,b)=gcd(b,r)。 第一步:令c=gcd(a,b),则设a=mc,b=nc 第二步...
  • 两个数互素的性质告诉你一个更一般的定理吧:整数a,b,最大公因数d,则存在整数m,...辗转相除法:设两数为a、b(b),求它们最大公约数(a、b)的步骤如下:用b除a,得a=bq1+r1(0≤r)。若r1=0,则(a,b)=b;若r1≠0,...
  • 什么是辗转相除法?    在求解2个整数的最大公约数时,每次将余数作为除数,上一次的除数作为被除,直到余数为0时,得到的除数即为辗转相除得到的最大公约数。  &emsp 举个栗子: 用辗转相除法计算 60和250的...
  • 辗转相除

    千次阅读 2018-07-26 16:12:45
    最近闲来无事,把之前学过的复习一下,什么叫辗转相除法呢(以下来自百度百科) 辗转相除法, 又名欧几里德算法(Euclidean ...如果的最大公约数,那么最后的除数就是这的最大公约数。  从以上...
  • 写在前面:本着弄懂每一个小知识点的学习原则,打算彻底理清一下辗转相除法。 1 什么是辗转相除法? 辗转相除法,又称欧几里得算法…… ...首先我们给定 并且约定 : 如果 ,则 如果 ,则...
  • 【C语言】辗转相除

    2021-04-14 11:57:45
    公约数是什么?这个首先我们需要清楚。它是指能够同时整除几个整数的,在这个题目里,便是能同时整除个数字的。而最大公约数则是指,在上述的基础上,加上一个最大,即在公约数里找到最大的。 那么我们先...
  • 辗转相除求最大公约数

    千次阅读 2018-05-22 22:08:28
    什么叫辗转相除法求最大公约数辗转相除法求的最大公约数的步骤如下:先用大的一个除大的一个,得第一个余数;再用中较小的一个除第一个余数,得第二个余数;又用第一个余数除第二个余数,得第三个...
  • 1、什么是最大公约数 最大公约数指的两个或多个整数共有约数中最大的一个。 如果数a能被数b整除,a就叫做b的...即两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。 如(50,85): 因为...
  • 可以看到整体的过程就是对于a和b,进行一个a mod b,b mod (a mod b)的的过程,上面的情况说明,对于a和b来说,他们的最大公约数就等于b与(a mod) b的公约数,这就很有意思了,为什么呢。 来看证明: ...
  • 求最大公约数(辗转相除法)什么是最大公约数?原理代码递归升级版(DP)总结 什么是最大公约数? 两个数的最大公约数指能同时整除这两个数的最大正整数 原理 设两数为a、b(a≥b),求a和b最大公约数的步骤如下: (1)...
  • 辗转相除一种快速求最大公约数的一种算法,其核心的思想 gcd(a,b) = gcd(b, a mod b)。至于为什么这样,本文就给出证明过程。 题目 证明 gcd(a, b)=gcd(b, a mod b) ,其中 a,ba, ba,b 正整数,函数 ...
  • 数学扫盲----辗转相除

    2018-06-20 14:47:01
    是什么它是已知最古老的算法,可追溯到公元前300年。它首次出现于欧几里得的《几何原本》中,而在中国则可以追溯至东汉出现的《九章算术》。用现代数学的术语来说,就是欧几里得算法采用的方法是重复下面的等式,...
  • 辗转相除法最简单最通俗证明

    千次阅读 2017-11-13 22:39:29
    先上辗转相除的代码 while (true) { int t = a % b; if (t == 0) break; else { ...为什么要这么做?...a,b,(a>b),肯定有一个公因数1的,或者也可能有一个更大的公因数z。不管1还是更大的,
  • 前言对0和1的操作计算机最底层的操作,所有的程序不管用什么语言写的,都要转化成机器能够读懂的语言也就是二进制进行基本的运算,而这些基本的运算就是我们今天要讲到的位运算。因为硬件的支持,计算机在进行二...
  • 辗转相除  好像没什么好说明的,就放一个百科吧。。。  辗转相除法, 又名欧几里德算法(Euclidean algorithm),求最大公约数的一种方法。它的具体做法:用较大数除以较小数,再用...另一种求两数的最...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 170
精华内容 68
关键字:

两数相除是什么