# 一篇文章搞懂面试中leetcode位操作算法题Single Number落单的数落单的数 IISingle Number IISingle Number III落单的数 IIINumber of 1

• Single Number落单的数
• 落单的数 IISingle Number II
• Single Number III落单的数 III
• Number of 1 Bits
• Counting Bits
• Reverse Bits
• Missing Number
• Sum of Two Integers
• Power of Two
• Power of Four

# Single Number落单的数

```public class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i=0;i<nums.length;i++)
res ^= nums[i];
return res;
}
}```

# 落单的数 IISingle Number II

```public class Solution {
public int singleNumber(int[] A) {
int[] bits = new int[32];

int res = 0;

for(int i=0;i<32;i++) {
for(int j=0;j<A.length;j++) {
bits[i] += (A[j]>>i) & 1;
}

res = res | ((bits[i]%3) << i);
}

return res;
}
}```

# Single Number III落单的数 III

```public class Solution {
public int[] singleNumber(int[] A) {
int xor = 0;

for(int i=0;i<A.length;i++) {
xor ^= A[i];
}

// a&(a-1)将最后为1的一位变成0

int lastbit = xor - (xor & (xor -1)); //取出最后一个为1的位

int group0 = 0, group1 = 0;

for(int i=0;i<A.length;i++) {
if((lastbit & A[i]) == 0)
group0 ^= A[i];
else
group1 ^= A[i];
}

return new int[]{group0,group1};
}
}```

# Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight). For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011 , so the function should return 3.

```public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int ones = 0;
while(n!=0) {
ones += (n & 1);
n = n >>> 1;
}
return ones;
}
}```

```public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int sum = 0;

while(n != 0) {
sum++;

n = n & (n-1);
}
return sum;
}
}```

# Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example: For num = 5 you should return [0,1,1,2,1,2].

image.png

```public class Solution {
public int[] countBits(int num) {
int[] res = new int[num+1];

for(int i=1;i<=num;i++)
res[i] = res[i>>1] + (i & 1);

return res;
}
}```

# Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

```public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int x) {
x = ((x & 0xaaaaaaaa) >>> 1) | ((x & 0x55555555) << 1);
x = ((x & 0xcccccccc) >>> 2) | ((x & 0x33333333) << 2);
x = ((x & 0xf0f0f0f0) >>> 4) | ((x & 0x0f0f0f0f) << 4);
x = ((x & 0xff00ff00) >>> 8) | ((x & 0x00ff00ff) << 8);
x = ((x & 0xffff0000) >>> 16) | ((x & 0x0000ffff) << 16);
return x;
}
}```

# Missing Number

```public class Solution {
public int missingNumber(int[] nums) {
int xor = 0, i = 0;
for (i = 0; i < nums.length; i++) {
xor = xor ^ i ^ nums[i];
}

return xor ^ i;
}
}```

# Sum of Two Integers

```class Solution {
/*
* param a: The first integer
* param b: The second integer
* return: The sum of a and b
*/
public int aplusb(int a, int b) {
// write your code here, try to do it without arithmetic operators.
if(a==0)return b;
if(b==0)return a;
int x1 = a^b;
int x2 = (a&b)<<1;
return aplusb(x1,x2);
}
};```

# Power of Two

Given an integer, write a function to determine if it is a power of two. 要为2的次方 1，2，4，8，16 也就是每位分别单独为1 1 10 100 1000 10000 所以n & (n-1)必须为0

```public class Solution {
public boolean isPowerOfTwo(int n) {
if(n<=0)
return false;
return (n & (n-1)) == 0;
}
}```

# Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4. 按照上一题的思路，我们先列举出几个4的次方数，观察他门的规律 1 100 10000 1000000 我们发现不仅要2的次方的性质，还要满足 1所在的位必须是奇数位，所以我们取出奇数位，由于，1只在奇数位，所以取出奇数位后，应该还和原来的数相等 取奇数位的方法在反转bit那题中已经讲过，就是x & 0x55555555

```public class Solution {
public boolean isPowerOfFour(int num) {
return (num > 0) && ((num & (num - 1)) == 0) && ((num & 0x55555555) == num);
}
}```

0 条评论

13710

9420

8720

16940

22730

10540

10420

10120

2.6K160

9420