Google电面的Bit操作题, 问你能不能用一个O(1)的方法, 判断n是不是4的倍数. 既然是O(1), 所以不能用循环, 先把n对n-1取&, 假设n = 16, 即10000. n-1=15,即01111. 但是我们还需要判断这个数是不是0. 所以我们让n对一个比它小的质数取mod. 比如4%3==1, 这样就可以判断n是不是4的倍数了. public static boolean isPowerof4(int n) { return (n&n-1)+n%3==1; } 下边是power of 8 public static boolean isPowerof8(int n) { return (n&n-1)+n%7==1; }
Bit操作的题, 给一个整数+1,不能用加号. 其实很简单,扫一下整数的每个bit(从低位到高位), 对它做&操作, 如果结果是0, 证明此位是0, 那么我们在这位+1, 如果是1, 那么我们清空此位. public class addBinaryNumberBy1WithoutPlus { public int add(int n) { for(int i = 0; i < 32; i++) { if (((1 << i) & n) == 0){ //until we find the first 1 bit n = n | (1 << i); break; } else n = n […]
1. 给个数组, 已经排序了, 找到第一个比n大的数. 如果没有, 返回-1. 二分搜索一下就可以, 注意一下返回-1的条件. public static int fixBox(int[] nums, int product) { int n = nums.length; int l = 0; int r = nums.length – 1; while (l <= r) { int mid = l + (r – l) / 2; if (nums[mid] < product) l = mid + 1; else […]