位运算面试问题

摘要

记得又一次面试,进行到最后一轮CTO面试。一般情况下领导基本都是闲聊一下,看看你的表达能力和性格。应该不会问什么技术难题,但这次真的被几个简单问题难住了。后面查了一下资料,原来都是关于“位运算”,这次刚好整理一下。

面试问题

  1. 如何在不使用乘以8的情况下,给一个数扩大8倍?(其效率比乘以8要高)
    我当时明白肯定是位运算的左移或者右移,不太确定具体是哪一个了。主要还是因为基本知识有没有理解。对于一个二进制的数据,左移一位扩大2^1,左移2位扩大2^2,右移肯定是除以的操作。具体的二进制为:

比如5的二进制位101,左移3位

(5)_{10} = (101)_2 <<< 3 = (101000)_2 = (2^5 + 2^3)_{10} = (40)_{10}
  1. 如何在不引入第三个变量的情况下,交换两个变量的值?
    我当时第一想法就是指针可以用于交换了两个变量,但是还是要引入第三个变量。从来没有见过这样的操作。我只能老实回答这个题不会。
    之后我查了资料,发现还是位运算的异或操作。

两个变量 x, y, x ^= y, y ^= x; x ^= y;通过这样三次异或操作就完成了变量的交换。

代码如下:

void swap(int x, int y) {
    x ^= y;
    y ^= x;
    x ^= y;
}
  1. 判断一个数是不是2的幂。
    我当时想到的思路就是使用循环除以2,并且判断余数。其实判断的效率基本没有什么问题,查阅资料才发现,用位与运算真的很骚。
boolean power2(int x) {
    return ((x&(x-1))==0)&&(x!=0);
}

因为所有的2的幂的数,二进制都是这样的:

10,100,1000,10000,100000,1000000…

这样的二进制数据与本身减去1以后再做位与操作刚好等于0,如果不是这样的数据,则不成立。这样运算效率不知要快多少倍。

总结

以前就是大概看了一下位运算,从来没有关注过如何使用。通过这次面试,确实学到挺多,位运算真的很骚,好像在生成hashcode的时候也使用了位运算。有空了再看一下。

关注机器学习和算法的码农,喜欢编程和读书
文章已创建 72

发表评论

电子邮件地址不会被公开。

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部