-
位运算判断奇偶数_面试 | 常见的位运算
2021-01-07 23:00:338:30 准时推送下面开始今天的学习~计算机中的数在内存中都是以二进制形式进行存储的,用位操作就是直接对整数在内存中的二进制位进行操作,因此其执行效率非常高,在程序中尽量使用位运算进行操作,这会大大提高...点击上方蓝字设为星标
每周一、三、五上午 8:30 准时推送
下面开始今天的学习~
计算机中的数在内存中都是以二进制形式进行存储的,用位操作就是直接对整数在内存中的二进制位进行操作,因此其执行效率非常高,在程序中尽量使用位运算进行操作,这会大大提高程序的性能。位操作是各大互联网公司面试经常会问的一类问题。
位操作符
& 与运算 两个位都是 1 时,结果才为 1,否则为 0,如
1 0 0 1 1
& 1 1 0 0 1------------------------------
1 0 0 0 1
| 或运算 两个位都是 0 时,结果才为 0,否则为 1,如
1 0 0 1 1
| 1 1 0 0 1------------------------------
1 1 0 1 1
^ 异或运算,两个位相同则为 0,不同则为 1,如
1 0 0 1 1
^ 1 1 0 0 1-----------------------------
0 1 0 1 0
~ 取反运算,0 则变为 1,1 则变为 0,如
~ 1 0 0 1 1
-----------------------------
0 1 1 0 0
<< 左移运算,向左进行移位操作,高位丢弃,低位补 0,如
int a = 8;
a << 3;
移位前:0000 0000 0000 0000 0000 0000 0000 1000
移位后:0000 0000 0000 0000 0000 0000 0100 0000
>> 右移运算,向右进行移位操作,对无符号数,高位补 0,对于有符号数,高位补符号位,如
unsigned int a = 8;
a >> 3;
移位前:0000 0000 0000 0000 0000 0000 0000 1000
移位后:0000 0000 0000 0000 0000 0000 0000 0001
int a = -8;
a >> 3;
移位前:1111 1111 1111 1111 1111 1111 1111 1000
移位前:1111 1111 1111 1111 1111 1111 1111 1111
常见位运算问题
1. 位操作实现乘除法
数 a 向右移一位,相当于将 a 除以 2;数 a 向左移一位,相当于将 a 乘以 2
int a = 2;
a >> 1; ---> 1
a << 1; ---> 4
2. 位操作交货两数
位操作交换两数可以不需要第三个临时变量,虽然普通操作也可以做到,但是没有其效率高
//普通操作
void swap(int &a, int &b) {
a = a + b;
b = a - b;
a = a - b;
}
//位与操作
void swap(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
位与操作解释:第一步:a ^= b ---> a = (a^b);
第二步:b ^= a ---> b = b^(a^b) ---> b = (b^b)^a = a
第三步:a ^= b ---> a = (a^b)^a = (a^a)^b = b3. 位操作判断奇偶数
只要根据数的最后一位是 0 还是 1 来决定即可,为 0 就是偶数,为 1 就是奇数。
if(0 == (a & 1)) {
//偶数
}
4. 位操作交换符号
交换符号将正数变成负数,负数变成正数
int reversal(int a) {
return ~a + 1;
}
整数取反加1,正好变成其对应的负数(补码表示);负数取反加一,则变为其原码,即正数
5. 位操作求绝对值
整数的绝对值是其本身,负数的绝对值正好可以对其进行取反加一求得,即我们首先判断其符号位(整数右移 31 位得到 0,负数右移 31 位得到 -1,即 0xffffffff),然后根据符号进行相应的操作
int abs(int a) {
int i = a >> 31;
return i == 0 ? a : (~a + 1);
}
上面的操作可以进行优化,可以将 i == 0 的条件判断语句去掉。我们都知道符号位 i 只有两种情况,即 i = 0 为正,i = -1 为负。对于任何数与 0 异或都会保持不变,与 -1 即 0xffffffff 进行异或就相当于对此数进行取反,因此可以将上面三目元算符转换为((a^i)-i),即整数时 a 与 0 异或得到本身,再减去 0,负数时与 0xffffffff 异或将 a 进行取反,然后在加上 1,即减去 i(i =-1)
int abs2(int a) {
int i = a >> 31;
return ((a^i) - i);
}
6. 位操作进行高低位交换
给定一个 16 位的无符号整数,将其高 8 位与低 8 位进行交换,求出交换后的值,如:
34520的二进制表示:
10000110 11011000
将其高8位与低8位进行交换,得到一个新的二进制数:
11011000 10000110
其十进制为55430
从上面移位操作我们可以知道,只要将无符号数 a>>8 即可得到其高 8 位移到低 8 位,高位补 0;将 a<<8 即可将 低 8 位移到高 8 位,低 8 位补 0,然后将 a>>8 和 a<<8 进行或操作既可求得交换后的结果。
unsigned short a = 34520;
a = (a >> 8) | (a << 8);
7. 位操作进行二进制逆序
将无符号数的二进制表示进行逆序,求取逆序后的结果,如
数34520的二进制表示:
10000110 11011000
逆序后则为:
00011011 01100001
它的十进制为7009
在字符串逆序过程中,可以从字符串的首尾开始,依次交换两端的数据。在二进制中使用位的高低位交换会更方便进行处理,这里我们分组进行多步处理。
第一步:以每 2 位为一组,组内进行高低位交换
交换前: 10 00 01 10 11 01 10 00
交换后: 01 00 10 01 11 10 01 00
第二步:在上面的基础上,以每 4 位为 1 组,组内高低位进行交换
交换前: 0100 1001 1110 0100
交换后: 0001 0110 1011 0001
第三步:以每 8 位为一组,组内高低位进行交换
交换前: 00010110 10110001
交换后: 01100001 00011011
第四步:以每16位为一组,组内高低位进行交换
交换前: 0110000100011011
交换后: 0001101101100001
对于上面的第一步,依次以 2 位作为一组,再进行组内高低位交换,这样处理起来比较繁琐,下面介绍另外一种方法进行处理。先分别取原数 10000110 11011000 的奇数位和偶数位,将空余位用 0 填充:
原数: 10000110 11011000
奇数位: 10000010 10001000
偶数位: 00000100 01010000
再将奇数位右移一位,偶数位左移一位,此时将两个数据相或即可以达到奇偶位上数据交换的效果:
原数: 10000110 11011000
奇数位右移一位: 0 10000010 1000100
偶数位左移一位:0000100 01010000 0
两数相或得到: 01001001 11100100
上面的方法用位操作可以表示为:
取a的奇数位并用 0 进行填充可以表示为:a & 0xAAAA
取a的偶数为并用 0 进行填充可以表示为:a & 0x5555 因此,上面的第一步可以表示为:
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1)
同理,可以得到其第二、三和四步为:
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2)
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4)
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8)
因此整个操作为:
unsigned short a = 34520;
a = ((a & 0xAAAA) >> 1) | ((a & 0x5555) << 1);
a = ((a & 0xCCCC) >> 2) | ((a & 0x3333) << 2);
a = ((a & 0xF0F0) >> 4) | ((a & 0x0F0F) << 4);
a = ((a & 0xFF00) >> 8) | ((a & 0x00FF) << 8);
8. 位操作统计二进制中 1 的个数
统计二进制1的个数可以分别获取每个二进制位数,然后再统计其1的个数,此方法效率比较低。这里介绍另外一种高效的方法,同样以 34520 为例,我们计算其 a &= (a-1)的结果:
第一次:计算前:1000 0110 1101 1000 计算后:1000 0110 1101 0000
第二次:计算前:1000 0110 1101 0000 计算后:1000 0110 1100 0000
第二次:计算前:1000 0110 1100 0000 计算后:1000 0110 1000 0000 我们发现,没计算一次二进制中就少了一个 1,则我们可以通过下面方法去统计:
count = 0
while(a){
a = a & (a - 1);
count++;
}
本文作者:Shawn
编辑&版式:霍霍
声明:本文归 “力扣” 版权所有,如需转载请联系。
-
通过位与运算判断奇偶数
2011-05-20 18:02:58一般判断奇偶数是用 num % 2 == 0 来判断,如果为true则为偶数,为false则为奇数。...所以可以通过与1做位与运算判断奇偶数。(num & 1) == 0 如果结果为true则为偶数,为false则为奇数。效率比取余运算高的多。...一般判断奇偶数是用 num % 2 == 0 来判断,如果为true则为偶数,为false则为奇数。
偶数在二进制里面,最后一位为0,奇数则为1。所以可以通过与1做位与运算判断奇偶数。(num & 1) == 0 如果结果为true则为偶数,为false则为奇数。效率比取余运算高的多。 -
位运算判断奇偶数_LeetCode进阶136-位运算巧用
2021-01-07 23:00:34概要有过开发经验的童鞋可能已经注意到,很多时候在Java标准库的源码中可以看到位运算的身影,本质原因是位运算能提高算法效率。在之前发布的博文中曾提到过原因LeetCode进阶-彩蛋一,也有一些实际运用的例子,比如...概要
有过开发经验的童鞋可能已经注意到,很多时候在Java标准库的源码中可以看到位运算的身影,本质原因是位运算能提高算法效率。在之前发布的博文中曾提到过原因LeetCode进阶-彩蛋一,也有一些实际运用的例子,比如按位与&判断奇偶数LeetCode进阶-1025(动态规划),移位<<(>>)和&结合存储数据存取LeetCode进阶-1029(贪心)。本篇将结束位运算中的异或运算^的巧妙用法。
原题
136. Single Number (Easy)
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1] Output: 1 Example 2:
Input: [4,1,2,1,2] Output: 4
- tag: Bit Manipulation
136. 只出现一次的数字 (简单)
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1] 输出: 1 示例 2:
输入: [4,1,2,1,2] 输出: 4
- 分类:位运算
题意分析&&思路设计
根据题意,需要找出数组中唯一的没有重复出现的整数。由于本篇是位运算实践科普篇,在分析之前先来看下^异或运算符的特性:第一个操作数的的第n位于第二个操作数的第n位 相反,那么结果的第n为也为1,否则为0。简单来说^运算有两个比较典型的应用特性:1、相同数字(整数)进行^运算结果为0。假设a=b,由于a和b每一位上的数字相同,因此最终a^b=0,结合本题。2、任何数字(整数)异或0,即n^0=n,同理可得。除了一个数字只出现了一次,其他任何数都出现两次。也就是[a,a,b,b,c,c...x,d,d,e,e..](列举示例,实际顺序忽略)中找出只出现一次的x。显然依次将所有数字进行^运算,利用相同数字n^n=0,x^0=x特点最后计算结果必然为只出现了一次的整数。
编码实践
public int singleNumber(int[] nums) { int res = 0; int len = nums.length; for (int i = 0; i < len; i++) { res ^= nums[i]; } return res; }
结语
本题属于位运算科普篇,属于位运算的基本技巧。最后,如果觉得本文对你有所帮助或启发那就来个赞吧0.0~
关注订阅号 获取更多干货~ -
JS:位运算简单总结与实用技巧
2019-02-20 19:48:17目录 位运算基础 按位与(&) 按位或(|) 按位非(~) 按位异或(^) 有符号左移(<...判断一个数是否为2的幂 ...位运算执行效率更高比一般的数值运算效率更高。 位运算基础 按位与(&am...目录
位运算执行效率更高比一般的数值运算效率更高。
位运算基础
按位与(&)
只有两个数的值为1时,返回1;其余返回0
应用:判断奇偶性
用数n和1进行按位&,速度比n%2快,即n&1
原理:奇数的二进制码最后一位一定为1,而1只有最后一位1,按位&之后,奇数&1结果为1,偶数&1结果为0.
按位或(|)
只要两个数中有一个数为1,返回1;其余返回0
应用:求整
浮点数n与0进行|运算,即n|1
原理:浮点数不支持位运算,先会被转化为整数再进行位运算
按位非(~)
求二进制的反码
有符号的32位二进制的最高位代表正负,1代表负数,0代表整数。
应用
十进制转换为二进制:(例如-2)
11111111111111111111111111111110 //最高位为1,是负数 10000000000000000000000000000001 //最高位不变,其余位取反 10000000000000000000000000000010 //加1,得到十进制为-2
二进制转换为十进制:(例如-5)
00000000000000000000000000000101 //5的二进制 11111111111111111111111111111010 //取反 11111111111111111111111111111011 //加1
按位异或(^)
两个数中只有一个1时返回1,其他情况返回0
应用:调换两个数字的值
var num1 = 1, num2 = 2; num1 ^= num2; // num1 = num1 ^ num2 = 1 ^ 2 = 3 num2 ^= num1; // num2 = num2 ^ (num1 ^ num2) = 2 ^ (1 ^ 2) = 1 num1 ^= num2; // num1 = num1 ^ num2 = 3 ^ 1 = 2 console.log(num1); // 2 console.log(num2); // 1
原理:数字与数字本身异或按位异或操作得到的是0
有符号左移(<<)
将二进制除了符号位的所有位向左移动指定位数,右侧补0
应用:求2的n次方
1<<n
有符号右移(>>)
将二进制除了符号位的所有位向右移动指定位数,右侧补0
求一个数的1/2:n>>1
无符号右移(>>>)
正数的无符号右移和其有符号右移结果一样,负数的无符号右移会移动符号位,而且无符号右移会把负数的二进制码当成正数的二进制码。
var num = -64; // 11111111111111111111111111000000
num = num >>> 5; // 134217726
应用:判断数的正负
n>>>0
原理:未移动位数,但负数的右移会将其变为正数。
-1>>>0 4294967295
console.log(-1>>>0); //4294967295
其他应用实例(待补充)
n&(n-1)
作用:将n的二进制表示中的最低位1改为0
如:n=10100 n-1 = 10011 n&(n-1)=10000
判断一个数是否为2的幂
n > 0 && ((n & (n - 1)) == 0 )
2的幂:二进制表示中只有一个1
如n = 1000 n-1 = 0111 则n&(n-1) = 0
求数中某一个数的二进制表示中1的个数
while (n >0 ) {
count ++;
n &= (n-1);
}
未完待续...
-
位运算
2019-09-29 16:11:41(按位与) 一个数&1结果为该数二进制表示中的最末位,可用于判断该数奇偶,0为偶数,1为奇数。 |(按位或) ^(按位异或) 相同为0,不同为1 优先级:& > ^ > | ~(按位取反) <&... -
位运算及其骚操作
2020-05-15 17:41:09计算机中的数在内存中都是以二进制形式进行存储的,用位运算就是直接对整数在内存中的二进制位进行操作,因此其执行效率非常高,在程序中尽量使用位运算进行操作,这会大大提高程序的性能。 补码 数值有正负之分,二... -
Java常用的位与或等运算
2020-08-05 10:53:57按位与运算, 判断该数值是否为2^n private static boolean isPowerOfTwo(int val) { return (val & -val) == val; } 如果线程池的线程数量是 2^n, 按位与效率较高 public EventExecutor next() { return ... -
js中位运算的运用实例分析
2020-12-12 23:26:08平时的数值运算,其实是要先转换成二进制再进行运算的,而位运算就是直接进行二进制运算,所以位运算的执行效率肯定是更高的。下面通过一些实例来加深对位运算的理解。 按位与(&) &&运算符我们都知道,只有两个都为... -
c通过位运算求绝对值_15种位运算的妙用,你都知道吗?
2020-12-03 03:02:43位运算在驱动开发中是经常遇到的,尤其是置0和置1。既要指定的位数发生变化,又不能改变其它位的值,还要高效率的编写代码,这时候技巧就很重要了。在位运算中有几个符号: | 按位或 、& 按位与 、 ^ 异或 、~... -
java位运算的应用场景举例
2021-01-25 09:20:25java位运算符介绍 Java位运算符是对操作数的二进制位进行运算,操作数和计算...位运算是直接操作二进制位,效率较高,一些算法会采用位运算。 奇偶判断是判断一个是奇数还是偶数,如何使用位运算实现呢? 使用与(& -
简单了解python的一些位运算技巧
2021-01-20 07:10:47位运算的性能大家想必是清楚的,效率绝对高。相信爱好源码的同学,在学习阅读源码的过程中会发现不少源码使用了位运算。但是为啥在实际编程过程中应用少呢?想必最大的原因,是较为难懂。不过,在面试的过程中,在... -
C语言高效位运算的妙用
2021-02-14 18:48:39文章目录高效位运算的妙用引言位运算符二进制补码运算公式应用乘法求余数判断奇偶性相反数求整数的绝对值交换整数判断一个数是否是2的幂求平均数掩码集合的表示 引言 计算机的存储器是采用二进制表示数据,直接用位... -
算法竞赛进阶指南-0x01 位运算
2020-12-18 01:22:45位运算是效率最高的运算模式,充满了技巧性。 按位运算 位与 位或 位反 位异或 & | ~ ^ 其中,与运算只要一端为0,结果为0,或运算只要一端为1,结果为1 异或运算当两端相异返回1否则为0 这里介绍一下... -
二进制位运算--写出2*8的最有效率的运算方法
2019-09-19 10:04:55用位运算效率最高了。 按位与(&) 相对应的二进制位同为 1 结果才为 1,否则都是 0,形如:0&0=0,0&1=0,1&0=0,1&1=1 。利用这个特性,我们判断奇偶数就可以不用再传统的... -
面试题中的位运算
2016-04-13 13:49:32为了提高代码的运行效率,可以用位运算代替常用的一些运算 用右移代替除以2,用左移代替乘以2; 用位与运算符代替求余运算符(%)来判断一个数是奇数还是偶数; 把一个整数减去1之后再和原来的整数做与运算,得到... -
性能优化利器-位运算的整理总结
2020-01-08 15:30:42关于位运算,相信大家都不陌生,特别是写过一些对性能要求很严苛项目的同学,毕竟,这是一把提升程序性能效率的神兵利器。 我们都知道,程序中所有的数在计算机内存中都是以二进制的形式储存的,而位运算就是直接对... -
高逼格的位运算小结
2019-06-01 21:26:25位算法的效率有多高这里就不讲了,位运算其实有很多技巧,比如判断是否是2的幂次方、判断奇偶性、交换两个数、找出不重复的数、找出不大于N的最大的2的幂指数,掌握这些可以装逼。 位与 & 两位... -
java界的10位大神_程序性能优化利器 - 位运算的使用技巧
2021-01-07 23:00:33前言关于位运算,相信大家都不陌生,特别是写过一些对性能要求很严苛项目的同学,毕竟,这是一把提升程序性能效率的神兵利器。我们都知道,程序中所有的数在计算机内存中都是以二进制的形式储存的,而位运算就是直接... -
位运算在java项目中的使用场景案例分析
2020-12-25 16:32:31位运算在java项目中的使用场景案例分析:位运算是计算机底层的操作,执行效率可以说是最高的,因此,项目中的功能如果能用位运算,就尽量使用;下面我们详细分析位运算在项目中的使用场景。 1、判断一个整数的奇偶... -
位运算——数0的个数
2016-05-07 12:17:53然后用N 同1进行“与”运算,来判断末尾是否为1 下面有更快的方法; 快速的方法:判断某一位置是否是1的一个方法,v&=(v-1); 最经典: 位操作比除、余操作的效率高了很多。但是,即使采用位操作,时间... -
输出n的最高位c++_LeetCode进阶136-位运算巧用
2020-12-02 10:20:55概要有过开发经验的童鞋可能已经注意到,很多时候在Java标准库的源码中可以看到位运算的身影,本质原因是位运算能提高算法效率。在之前发布的博文中曾提到过原因LeetCode进阶-彩蛋一,也有一些实际运用的例子,比如... -
&与&& ,|与|| 的区别以及“&”和“|”的位运算
2018-03-06 16:58:27不同点:执行的效率不一样 “&” 会 将判断条件全部执行一次,然后检测到单个条件的结果为 false 时,整体的结果就为 false ; “&&” 会由左往右执行条件,只要检测到判断结果为 false ... -
C/C++ 位运算 逻辑运算符和移位运算符
2020-07-01 23:16:16运算:**位运算时两边都是1时为1,否则为0 1&1 = 1 1&0 = 0 0&1 = 0 0&0 = 0 应用:&1可以用来判断一个数是奇数还是偶数 因为奇数的的二进制的最后一位必定是1,偶数是0 int型(32 -
csdner: 帅地, 【技巧总结】位运算装逼指南
2019-11-27 23:23:39位运算很多情况下都是很二进制扯上关系的,所以我们要判断是否是否位运算,很多情况下都会把他们拆分成二进制,然后观察特性,或者就是利用与,或, 非,异或, 移位的特性来观察,总之,我觉得多看一些例子,加上自己... -
“位运算”在程序开发中的妙用!
2012-10-08 15:27:46“位运算”虽然时计算机基本知识,但工作中一直没有用到它, 最近看Android源码时,经常会发现某些状态判断地方用到“位运算”,开始以为只是为了提高效率,感觉怪怪的,直接判断状态位或者布尔值判断不就行了,干嘛... -
判断输入的一个整数有多少位是1,效率要高
2017-03-03 19:58:40方法一:判断有多少个1,可以将一个数不断的和1相与,之后将此数的二进制向右移动一位这样就可以判断有多少个一 public int getSum(int n){ int count = 0; if(n&1){ count++; } return count; } 方法二:一... -
位运算的实际应用 【俩数字交换不借助遍历】【寻找1出现的次数】【如何判断一个整数为2的整数次幂】
2020-08-10 01:36:50两个数字交换位置,不借助临时变量 //: A UIKit based Playground for presenting user interface import UIKit var a = 10 var b = 8 a = a^b ...解题思路 与1与法 //: A UIKit based Playg.. -
一次遍历找出不同的数(位运算)
2018-03-29 14:31:20数字的范围:0~INT_MAX数字的个数:2~2000000个如输入1 2 3 2 2 3输出1 2使用数组记录出现次数,并且判断是否出现偶数次,效率较低。使用异或规则:a⊕b=b⊕a 交换律a⊕0=a 与0异或不变a⊕b⊕b=a 偶数次... -
c语言基础与提高(一)数据类型,混合运算,运算符,以及几种基本判断,循环语句
2018-07-21 21:44:45今天学习的内容内容比较多,为了节省十日,提高效率,di代码采用截图fa方式呈现,这样更直观,更明了,下面是jin'今天所学内容: 数据类型(32位操作系统中) int 4个字节 32位(一个字节8位) float 4个字节 ...
-
[Mercury landing-水星迫降] v4.0.7z
-
#关于属性名和字段名不一致报错的问题
-
心脏杂波识别筛查-源码
-
es6常见新特性汇总解读
-
generic-flonum:用于各种IEEE-754浮点格式的球拍包-源码
-
Galera 高可用 MySQL 集群(PXC v5.6 + Ngin
-
C 学习指南 - 语法篇.zip
-
MySQL 高可用工具 DRBD 实战部署详解
-
MySQL你该了解的那些事【服务端篇】
-
Windows系统管理
-
会员注册页面的交互细节
-
电影API-源码
-
想自学Python却不懂如何入门?看完这篇文章你就已经入门Python了
-
MHA 高可用 MySQL 架构与 Altas 读写分离
-
安监总局(2010)AQ2030-2010尾矿库安全监测技术规范.pdf
-
Mycat 实现 MySQL的分库分表、读写分离、主从切换
-
FTP 文件传输服务
-
data-analysis-using-python:使用Python进行数据分析:具有NYC开放数据的初学者指南-源码
-
个人发卡4套模板.zip
-
运维开发工程师(BKDS)理论基础