oi位运算

大家好，我刚刚入坑oi。。最近一段时间我会不定期更新我所学的oi知识点，可能会有所疏漏。如果有看见的请轻喷，我会抽时间改正。其中部分可能引用《算法竞赛进阶指南》《c++ primer plus第六版》。可能对某个知识点理解偏颇，也请各位指出。

在c++中，我目前所学的位运算包括有：与，或|，非！，异或^,左移，右移。

什么是按位与呢？在二进制表示下，ab当且仅当均为1时结果才为1.

按位或|，则是只要有一个为1，结果就为1。非则是假变真，真变假。与此对应的还有一个按位取反~，对二进制表示下每一位取反。接下来可以流畅的引出负数了。讲一下关于负数在计算机中的存储方式。我以32位无符号和有符号整数举例。

对于32位有符号整数，它会以最高位为符号位，其余位作存储用。在计算机中，对于负数它存储的是负数的补码。。我们先看下1在二进制表示下：0…1，中间省略N个0，它的补码就是反码+1，反码就是按位取反。则1……0，补码就是之后再加1，1…1。

下来讲下移位运算符：左移与右移。

左移: 在二进制表示下把数字向左移动n位，高位越界舍弃，低位补0.

左移一位相当于乘以2.其中有些人讲左移一位比乘以2要快，但是你如果看下它的汇编代码，其实，单纯的左移一位相当于乘以2效率没什么差别。。。

与此相对，既然有左移，肯定还有右移，想必你们都可以合理推断出，右移一位就是相当于除以2，而在c++实现中又分为逻辑右移与算术右移。。区别在于右移后高位的补充是否为符号位。。。

讲二进制怎么能不讲状态压缩。。。

二进制状态压缩：将一个01序列可以用一个数字保存，其中第i位是否为1表示了它是否存在。接下来列举一个我常用操作。。1：取出n在二进制表示下的第K位。 (nk)1. 先将n右移，之后再1。

讲了这么多，不上道例题怎么行。。

简要说明下题目，求a的b次方对k取模（取模，就是取余数。例如7对3取模就是1.7 / 3 = 2 余1）其中 ,1= a,b,k=10的9次方

很简单的一道入门题。。

int pow(int a,int b,int k){

int ans = 1 % k;//注意%k,因为可能因为一些数据卡掉，不信的可以在编译器尝试。

while （b）{

if (b1)ans = ans * a % k;

a = a * a % k;

b= 1;

}

return ans;

}

以上就是（oi位运算）全部内容，收藏起来下次访问不迷路！