位运算及其oj题

先注意一个点如果理不清位运算的优先级就一定要在执行运算时该带括号的带括号一.基础位运算x n:奉行多退少补的原则假设数据补码长度为8位将n的二进制下补码所有位向左移动n位并在右边补上n个0。此时统计位数如果超过8位则将最左侧超过的几位丢弃。相当于该数十进制下*2^neg:5 1 → 101 - 1010 → 十进制 105×25 2 → 101 - 10100 → 十进制 205×4-2 2 - 1111 1110 - 111 11000 - 十进制 -8 -2 * 4x n:将n的二进制下补码所有位向右移动n位并在左边补上n个符号位依旧要将右边超位数几位丢弃。相当于该数十进制下/2^neg:-8 2 - 1111 1000 - 1111 1110 - 十进制 -2 (-8 / 4),|,^:~:按位取反。对数据补码的每一位都取反包括符号位二.给一个数n确认它二进制的第x位是0还是1为了方便观察我们假设将n二进制每一比特位倒置在一个数组里那么它的下标就代表它是第几位。随后将n右移x个位置即把第x个位置移到最后一位,然后再将右移以后的n与1按位与()两个数按位与的规则是将两个数化成二进制每一位一一对应有0则是0。假如数据位数为32位最终结果为1则第x位是1。三.将n二进制表示的第x位修改为1将x位的数按位或(|)一个1其余数字要保持不变就按位或上一个0。要获得满足前面要求的一个数该怎么办呢只需将1x就行。随后用n|(1x)即可完成修改。相当于把1挪到第x位然后再进行按位或。二三实操只出现一次的数Ⅱhttps://leetcode.cn/problems/single-number-iihttps://leetcode.cn/problems/single-number-iin是所有数中除a以外其余数的种类之和。除a以外其余数均出现三次因此他们的总数是3n。注同一位置指的是同一比特位。将同一比特位所有数之和%3得到的结果与a在同一比特位下的值一一对应根据以上的信息我们可以得到算法1.求和:实际是求该位下1的个数。2.用每一位的和分别%3结果便得到a在同一位下对应的数字再用取模的结果依次修改ret的每一位最终ret的每一位就表示a的二进制下的每一位。就得到了a。3.求和和修改操作就用到了二三两个小巧思。其中求和的思想是先确认第i位的数是0是1如果是1就sum,以达到统计1个数的目的。而修改操作则是在ret初始值为0的前提下假如确定第i位a所对应的数字位1也就是和模3的值为1就把ret第i位的值改为1。class Solution { public: int singleNumber(vectorint nums) { int ret 0; for(int i 0;i 32;i)//遍历int每一位并完成ret的修改。 { int sum 0;//统计每一位所有数之和。 for(auto e: nums)//求nums里所有数第i位的和 { if(((e i) 1) 1) sum; } sum % 3; if(sum 1) ret | 1 i;//修改 } return ret; } };其实我们可以设计通法n个数相同在求和取模的时候就模n四.将一个数n的二进制数表示的第x位修改为0将n的二进制形式上一个除了第x位是0其余位均为1的二进制数。那么怎么保证该二进制数,除了第x位是0其余全为1呢答案是将1左移()x位的结果取个反(~)就行了五.lowbit注意-n是先对n按位取反然后再加1的成果。六.干掉n二进制表示中最右侧的1n-1时会去前面的位借位一直借到最右边的那个1处停止此时最右边的1就会因借位变成0。本质七.异或(^)操作的运算率注意异或玩的就是不进位相加。然后它满足交换律和结合率。