精华内容
下载资源
问答
  • 二进制算法--指数取余( (m^n)%k=? )

    千次阅读 2018-08-11 16:27:19
    描述:m,n,k,为整数,求 (m^n)%k=? 正经代码: #include<stdio.h> using namespace std; int main(){ int m,n,k; scanf("%d%d%d",&...=1,m=(long long)m...

    描述:m,n,k,为整数,求 (m^n)%k=?


    正经代码:

    #include<stdio.h>
    using namespace std;
    int main(){
        int m,n,k;
        scanf("%d%d%d",&m,&n,&k);
        int ans=1;
        for(;n;n>>=1,m=(long long)m*m%k)
            if(n&1)
                ans=(long long)ans*m%k;
        printf("%d\n",ans);
        return 0;
    }
    

    代码牛皮*:

    #include<stdio.h>
    #include<iostream>
    using namespace std;
    int main(){
        int m,n,k;
        scanf("%d%d%d",&m,&n,&k);
        int ans=1;
    cout<<"m="<<m<<"  n="<<n<<"  k="<<k<<endl;
        for(;n;n>>=1,m=(long long)m*m%k){
    cout<<"  --------\n  n="<<n<<endl<<"  n>>1 ="<<(n>>=1)<<endl;
    cout<<"  m="<<m<<endl;
            if(n&1)
                ans=(long long)ans*m%k;
    cout<<"  n&1="<<(n&1)<<endl<<"  ans="<<ans<<endl;
        }
        printf("%d\n",ans);
        return 0;
    }
    

    运行结果1,2,3,:


     


     

     

     

     

    展开全文
  • 快速幂(二进制)取模运算

    千次阅读 2020-02-07 16:24:46
    二进制的位运算,在此就不赘述,有问题的同学请自行百度,这里我们需要用到“&”与“>>”运算符。 先来一段具体代码,由代码来讲解 ll binaryPow ( ll num , ll k ) { ll ans = 1 ; while ( k > ...

    最近在牛客第一次碰到有关快速幂的知识,在此记录加深理解一下。大佬勿进,我怕《《 》》

    快速取幂的用途

    在一些竞赛中,可能会遇到指数型的数据取模问题,这个时候直接用int或者long long 储存,就非常有可能超出计算机整数的存取范围(哈哈,一般都会超,毕竟是竞赛!!!),从而数据出错,所以我们就引出今天的主角色 快速幂取模。这种方法在时间和空间都做了尽可能的优化,非常好用哦!

    快速幂取模的思路分析

    基本理论是离散数学的知识*(数学很重要!)*
    有一个引理我们需要清楚的:积的取余等于取余的积的取余。
    公式:(ab)%c = (a%c)(b%c)%c
    核心思想是将大数幂运算拆解成相应的乘法运算,利用上述式子,始终将我们的运算的数据量控制在c的范围下。

    以求a的b次方来介绍
    把b转换成二进制数。
    例如在这里插入图片描述
    11的二进制是1011
    在这里插入图片描述对二进制的位运算,在此就不赘述,有问题的同学请自行百度,这里我们需要用到“&”与“>>”运算符。

    先来一段具体代码,由代码来讲解

    ll binaryPow(ll num, ll k) 
    {
     ll ans = 1;
     while(k>0)
     {
      if(k&1)
       ans = ans*num%mod;//如果k的二进制位不是0,那么就会进行该步
      num = num*num%mod;//不断加倍
      k >>=1; //相当于每次除以2,用二进制看,不断的遍历k的二进制位
     }
     return ans;
    }

    在上面的代码中,k&1意思就是取k的二进制的最末位,11的二进制数为1011,第一次循环,取的是最右边的1,以此类推。k>>=1意思就是k右移一位,删去最低位置。
    接下来我来说说while循环中的原理。
    以num^11为例子,k = 11
    k 的二进制 1011。
    我们要理解num = num * num;这一步的作用。
    在这里插入图片描述哎嗨,快速幂就讲解完了。希望大家可以共同进步。另外注明一点,代码%mod也是为了防止溢出,这是从下面一道训练题想出来的。
    下面贴出来一道例题。
    题目链接
    https://ac.nowcoder.com/acm/contest/3003/G

    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const int maxn = 200005;
    const int mod = 1e9+10;
    typedef long long ll;
    ll binaryPow(ll num, ll k) 
    {
     ll ans = 1;
     while(k>0)
     {
      if(k&1)
       ans = ans*num%mod;
      num = num*num%mod;
      k >>=1; 
     }
     return ans;
    }
     
    int main()
    {
     ios::sync_with_stdio(false);
     int t;
     cin >> t;
     while (t--)
     {
      long long a, b, c, d, e, f, g;
      cin >> a >> b >> c >> d >> e >> f >> g;
      int sum = 0;
      int m = 1e9 + 7;
      if (binaryPow(a,d)+binaryPow(b,e)+binaryPow(c,f) == g)
      {
       cout << "Yes" << endl;
      }
      else
      {
       cout << "No" << endl;
      }
     }
     return 0;
    }

    就这样吧,溜走。

    展开全文
  • 二进制基础运算整理

    2020-11-27 19:34:05
    在正常的运算规则下,我们熟悉的十进制会转化成二进制在计算机中表示,这时的二进制就是原码表示,在计算机中,为了简化运算单元的逻辑处理、降低硬件电路复杂度和成本,只有加法器的硬件电路,计算机的减法是通过...
    • 原码、反码和补码

      在正常的运算规则下,我们熟悉的十进制会转化成二进制在计算机中表示,这时的二进制就是原码表示,在计算机中,为了简化运算单元的逻辑处理、降低硬件电路复杂度和成本,只有加法器的硬件电路,计算机的减法是通过数学变换把其转化成加法运算,比如5-2,也就是5+(-2),但是如果用原码形式去运算5+(-2)得到的值却不是我们想要的值,所以经过探索,又出现了反码和补码,至于他们有什么作用,继续往下看。

      • 原码

        原码就是真值的二进制表示,最高位表示符号位,整数的符号位是0,负数的符号位是1。

        比如十进制真值是6,那么八位二进制的原码就是00000110,最高位是0表示正数;十进制的-3的八位二进制表示为10000011,最高位1表示负数。6-3 = 6+(-3) = 00000110+10000011 = 10001001 = -9,很显然它不是正确值3。

      • 反码

        反码的规则是正数的反码是它本身,负数的反码是符号位不变,其余位取反。

        还是上面的例子,6+(-3)的反码表示为00000110 + 11111100 = 100000010,最高位符号位溢出舍掉,即00000010 = 2 ,因为舍弃后的最高位是0,所以不需要再取反恢复成原码,但这也不是正确结果3,但是他们之间好像有点联系,-3原码10000011和其反码11111100,一个是-3,一个是-124,很多资料都是在补码的时候引入“同余”的概念,但我觉得在反码的时候引入更合理,因为在我看过一些资料之后,我还是不明白为什么是从反码过渡到补码而不是直接从原码到补码。

        • 同余和模的概念

          那同余的概念就是两个数对同一个固定的值取余的结果是一样的,则说明这两个值是同余的关系,这里的固定值通常是指一个系统中的最大值,类比生活中的钟表,在钟表系统中,最大值就是12,过了十二就又会从1开始,如果此时的时间是3点整,那么要修改成6点有两种方式,一种是顺时针拨到6点,此时指针走了3圈,另一种是逆时针拨到6点,此时指针走了9圈,那么3和9就是对于12的一对同余数,12就是这个系统的模。

        • 思想带入二进制

          回到八位二进制,因为八位二进制的最高位是符号位,所以它的真值表示范围就是-127~127(即11111111~01111111),负数范围相当于逆时针,正数范围相当于顺时针,所以它的模应该是127,但并不是,因为相对于钟表,它多了一个0,钟表的12就等于0,0就等于12,所以它的模就是12,而这里的八位二进制的0和127不表示同一个值,所以它的模应该是127+1 = 128。

        • 按位取反就是得到同余数

          前面的-3和-124就是原码反码的关系,按照钟表环形系统的模定义来说,把0和-127两端连接起来,这个点假设叫x,那-3到x的距离在两个方向上的前进步径分别是-3和124(这里假设-3、-2、-1、0的方向是负方向,-3、-4、-5…-127的方向是正方向),所以按位取反就是取得同余数的绝对值。

        经过上面的分析,那么上面的-3的反码-124少加个一个值(0),所以应该是-125,也就是11111101,那最后的结果就是00000011 = 3,这正是我们的正确结果。

      • 补码

        正数的补码是它本身,负数的补码等于其反码+1,之所以加1就是因为二进制和钟表不一样的它是线性结构,-127和0不是同一个值,所以我觉得补码的补在于补差的那个0,同余的概念应该存在于反码的按位取反中,负数x的补码的绝对值也就是2的n次幂+x(注意x是负数)。

    • 逻辑位运算符&、|、~、^、<<、>>

      在很多源码的阅读中,较深入的部分、接近底层的部分都会看到一些二进制中的逻辑运算符,有的时候简单的逻辑运算符就能表达一种动作、一个含义,出于求知欲,这里整理一下基本的逻辑运算符的意义和在开发中他们通常来做些什么。

      • 与运算‘&’

        两个二进制位相与,二者都为1的时候才得1,比如1101&0111 = 0101。

      • 或运算‘|’

        两个二进制位相或,有一个为1即得1,比如1101 | 0001 = 1101。

      • 异或运算‘^’

        两个二进制位异或运算,二者不同才得1,比如1101 ^ 0111 = 1010。

      • 非运算‘~’

        单目运算符,一个二进制位非运算,本以为是按位取反,其实并没有这么简单,c语言中unsigned修饰的整型非运算就相当于按位取反,但是对于非unsigned修饰的整数来讲,比如java中的整型都是有符号的,这些有符号的整数进行非运算的结果却别有洞天,比如在java中~5得到的却是-6,而按照按位取反的逻辑它应该是010=2。

        原因在于无符号的数都是正数,相当于你取反的值就是你的真值,但是有符号数的运算是带着符号位一起做的,比如说有符号数5,二进制应该是0101,最高位0代表正数,~运算会转成1010,因为是正数,所以补码也是这个,计算机的有符号数都是通过补码运算的,无论是不是负数,所以这里会把1010当成负数补码对待,那它的真值就是1110=-6,这就是~5 = -6的由来。

      • 左移‘<<’

        二进制所有位整体左移若干位,若高位溢出则舍弃,低位补0。

        比如5 << 1= 101 << 1 = 1010 = 10,可以发现这里的10是5的2倍,101 << 2 = 10100 = 20,所以左移n位就是扩大至原来的2的n次幂倍。

      • 右移‘>>’

        和左移相反,整体右移n位,数值减小2的n次幂,如果是正数,左边补0,如果是负数左边补1,因为是整型,所以会舍弃小数点后面的,譬如5>>1 = 101>>1=10 = 2。

      • 无符号右移‘>>>’

        相比于>>,不同的是左边都是补0。

      • 实际开发场景应用

        现在考虑一个场景,Java中有4个int型变量NONE = 0 = 00、A = 1 = 01、B = 2 = 10、ANY = 3 = 11,他们分别代表不同的模式,可能需要通过switch根据这个模式去做不同的事情,ANY = A | B,NONE = A & B,那么假设现在传进来一个mode是x,我们要求x是A或者ANY,那么可以通过x & A != 0 来确定。这种方式就是通过按照不同的二进制位来代表不同的东西,通过逻辑运算判断属不属于。

        实际RxJava中requestFusion用到了这种方式:

        @Override
        public int requestFusion(int mode) {
            if ((mode & ASYNC) != 0) {
                outputFused = true;
                return ASYNC;
            }
            return NONE;
        }
        
      • LeetCode中的一个题

        给定一个包含n+1个整数的数组,其数字在1到n之间,内部存在唯一的一个重复数,请找出它。

        做法有很多种,我们这里使用位运算符来做:

        int test(int[] nums){
          int base = 0;
          for(i : nums){
            if(base == (base | (1 << i)))
              return i;
            base |= (1 << i);
          }
        }
        

        首先从第一个元素开始,比如是3,则1<<3 = 1000,base|1000 = 1000,不相等,所以base = 1000,此时第4位已经是1了,表示这个位置有过记录了,假如再次读到3的时候,还是只是会在第4位变成1,也就是说读到重复数的时候,同样位置的二进制位已经变成过1了,base | (1 << i)和之前的base才会相同。

    展开全文
  • 取模运算与取余运算的相同点 公式相同: 取模运算: A mod B = A - (A / B) * B 取余运算: A rem B = A - (A / B) * B 取模运算与取余运算的不同点 对于 A / B 的定义不同: 取模运算在计算 A / B 的值时,向...

    取模运算与取余运算的相同点

    • 公式相同:

      取模运算: A mod B = A - (A / B) * B
      取余运算: A rem B = A - (A / B) * B

    取模运算与取余运算的不同点

    • 对于 A / B 的定义不同:

      取模运算在计算 A / B 的值时,向负无穷方向取整(floor()函数)
      取余运算在计算 A / B 的值时,向0 方向取整(fix()函数)

    • 举例说明:

      -3 / 2 = -1.5
      取模运算时,将 -1.5 向负无穷方向取整,得到 -2
      取余运算时,将 -1.5 向0方向取整,得到 -1

      所以,
      -3 mod 2 = -3 - (-2) * 2 = 1
      -3 rem 2 = -3 - (-1) * 2 = -1

    总结

    取余运算与取模运算在两数为同号时,结果相同;当两数异号时,结果不同。

    展开全文
  • 椭圆曲线加密体系中二进制域内多项式基表示的求模算法解析
  • 快速幂&二进制&位运算

    千次阅读 2019-08-02 09:19:04
    好的标题就告诉我们该来的还是会来,学了十几年十进制现在告诉我要学二进制,但是这个东西很重要很重要,所以还是要重点记 part 1:什么是二进制二进制,是计算技术中广泛采用的一种数制,由德国数理哲学大师...
  • 二进制的 0 1 基数: 每个进制的基数 比如十进制是10 二进制是2 二进制的位权:固定位置对应的单位值。比如一个数字从右往左从0开始递增 1.将二进制数转换成十进制 转换规则: 展开位权进行求和运算 100110 1x2^5+0x...
  • 二进制运算

    千次阅读 2019-03-10 16:27:06
    1.十进制转化为二进制(编译器为32进制) #include&amp;amp;lt;iostream&amp;amp;gt; using namespace std; int main() { int m,number ,s[32]; cin&amp;amp;gt;&amp;amp;gt;number; for...
  • 题目:来源于http://poj.org/problem?id=1060 描述:  定义二进制多项式加法和减法 :   (x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = x^7 + x^6 + x^4 + x^2  (x^6
  • 文章目录十进制转二进制机器数与真值原码、反码、补码顺便说一说BCD码数的定点表示与浮点表示IEEE 754标准定点运算加法与减法运算溢出浮点运算加法与减法运算 十进制转二进制 正整数转二进制,这个简单,除2取余,倒...
  • 二进制基础及位运算

    2019-12-04 16:06:09
    二进制计算 每一位上的数基数的索引次幂相加之和 例如:0101=12º+12²=5 第一位1基数2的索引0次幂+第三位1*基数2的2次幂等于5 其他进制计算等同 十进制转2进制:除2求余法 除2求余倒序表示 简便算法:记住2的10次...
  • 16进制是否能整除 求余的运算

    万次阅读 2019-10-30 09:26:43
    #include <stdio.h> void main() { int c,d; int a=0xb0,b=4; c=a%b; d=a/b; if(a%b==0) { printf("%d能被%d整除。",a,b); } if((a%b)!=0) { printf("%d不能被%d整除。",a,b); printf("\n %d",c);...i...
  • #include <iostream> using namespace std;... // 取余 n = n >> 1; //右移一位 相当于除以2 if(0 != n) { BinaryRecursion(n); } cout<<a; } int main(int argc, char *argv[])
  • 关于与运算取余之间的关系

    千次阅读 2015-10-14 19:34:06
     和3进行与运算,是取该数2进制形式的最后2位的值,因为3的二进制形式是(假设该数用1个字节表示,多个字节也一样,这里为了讲述,暂举1个字节为例)00000011,最后两位和1进行与,则把该数最后2位的状态取出来(和1与的特性,...
  • 十进制数转换为二进制数、八进制数、十六进制数的方法: 二进制数、八进制数、十六进制数转换为十进制数的方法:按权展开求和 与十进制 (1)二进制转十进制 方法:“按权展开求和” 【例】: 规律:...
  • php 实现二进制加法运算

    千次阅读 2014-05-16 15:03:49
    前些天去面试,面试官问我用php实现二进制的加法运算。虽然不知道应用场景,但也见怪不怪了,百度出来的人竟问这些个问题,回来自己也总结了下这方面的东西: 定义:
  • C++中取余运算的优化

    千次阅读 2019-09-16 10:39:39
    用-O3来编译所有的软件包将产生更大体积更耗内存的二进制文件,大大增加编译失败的机会或不可预知的程序行为(包括错误)。这样做将得不偿失,记住过犹不及。在gcc 4.x.中使用-O3是不推荐的。 -Os:这个等级用来优化...
  • 在学习框架源码底层时,有非常多的二进制运算,由于大学学习计算机基础时抓梦脚(jio),没有学习牢固,所以在看底层源码的算法逻辑时遇到二进制 运算比较吃力,遂通过一篇博文来总结下二进制运算,记录一下。 正文 ...
  • 进制转换:二进制、八进制、十六进制、十进制之间的转换 不同进制之间的转换在编程中经常会用到,尤其是C语言。 将二进制、八进制、十六进制转换为十进制 二进制、八进制和十六进制向十进制转换都非常容易,就是...
  • 二进制补码到十进制补码及其内的运算——关于补码的一点学习
  • 参加运算的两个数据,按二进制位进行“与”运算运算规则:0&0=0;0&1=0;1&0=0;1&1=1; 即:两位同时为“1”,结果才为“1”,否则为0 例如:3&5即 0000 0011 & 0000 0101 = 0000 0001...
  • 先给大家送个福利! ---------------简单口算-------------------------- ...十进制转二进制规则是:除二取余倒写 10 10/2 0 5/2 1 2/2 0 1 */ ------------------------------------------干货------...
  • 二进制加,减法,23个位运算技巧

    千次阅读 2019-04-06 20:36:22
    二进制加,减法 二进制最高位为1时表示负数,为0时表示正数。 **原码:**一个正数,转换为二进制位就是这个正数的原码。负数的绝对值转换成二进制位然后在高位补1就是这个负数的原码。 举例说明:  int类型的 3 的...
  • 快速幂和取余运算

    2019-07-05 21:17:00
    首先将指数转换为2进制,如\(2^{11}\),指数11的二进制为1011,即\(8+2+1\),可以得到\(2^{11}=2^8+2^2+2^1\)。...1.题目来源洛谷:P1226 【模板】快速幂||取余运算 实现代码如下: #include<iostre...
  • 运算&的取余操作

    千次阅读 2020-05-23 16:13:56
    取余的操作 i = (n - 1) & hash,这里的n是哈希桶的个数。 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = ...
  • 以十进制的“19”转换为二进制数为例,用19除以模(在这里模就是2)然后取它的余数。 19除以2商9余1 9除以2商4余1 4除以2商2余0 2除以2商1余0 1除以2商0余1 当商为0时结束运算 所以19的二进制为11001
  • C语言进制运算详解 2

    千次阅读 2020-04-18 15:31:41
    数字 0、1、10、111、100、1000001 都是有效的二进制二进制加法:1+0=1、1+1=10、11+10=101、111+111=1110 二进制减法:1-0=1、10-1=1、101-11=10、1100-111=101 八进制加法:3+4=7、5+6=13、75+42=137、2427+...
  • 整数部分,把十进制转成二进制一直分解至商数为0。读余数从下读到上,即是二进制的整数部分数字。 小数部分,则用其乘2,取其整数部分的结果,再用计算后的小数部分依此重复计算,算到小数部分全为0为止,之后读所有...
  • 二进制  正整数的二进制表示 (假定类型是byte)  正整数的二进制表示与此类似, 只是在十进制中,每个位置可以有10个数字,从0到9,但在二进制中,每个位置只能是0或1。  例如: 0000 1010 ==> 10 负整数...
  • 一、基本理论 ...1、思想:给定一个十进制数,我们可以通过移位来得到其对应的二进制数。  例如:对于long类型的十进制数1024,在32位计算机上,其二进制表示为  (00000000 | 00000000| 00000100|00000000)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,894
精华内容 8,757
关键字:

二进制取余运算