It's the Xinrui Ma

Blog

Tag: Bit Mainpulation

476. Number Complement

Posted by in LeetCode on

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.
Example 1:
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
Example 2:
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

461. Hamming Distance

Posted by in Java LeetCode on

Total Accepted: 36432
Total Submissions: 51340
Difficulty: Easy
Contributors: Samuri
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

The above arrows point to positions where the corresponding bits are different.

389. Find the Difference

Posted by in LeetCode on

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Solution: Same as find the single number, just be aware that the first character.

371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

So, the sum of a + b is also the sum of two parts, the carry and the sum without carry.

To get the sum without carry, just do a XOR,

To get the sum of carry, perform a AND operation and left shift 1 position.

Take this as an example.

5 + 7 = 12
||
101 + 111 = 1100

The part for carry only, 101 & 111 = 101, left shit 1 = 101 << 1 = 1010 the part for sum without carry, 101 ^ 111 = 010 The sum of 1010 and 010 = 1100 = 12 Code:

260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Answer:

Take a look at my previous post: http://maxinrui.com/index.php/2016/09/27/136-single-number-leetcode/

“Two same integers after XOR operation, the value is 0, and 0 XOR any integer is the integer itself”

Assume there are b and c that only appear once in the array, so, if we follow the same steps, perform XOR operation on each array elements, we could end up getting b ^ c;

What could b ^ c do for us?

It would be much simpler if the array can be split into two arrays that each only contain b or c, then we just do a XOR to all elements in each array, we could get the b and c.

That’s what b ^ c can do for us.

As we know, there must be a Kth bit of b and c that is different, otherwise they will be the same. Find the Kth bit that is different, we can use that to split the array into two arrays.

136. Single Number — LeetCode

Given an 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?

Thought:

I can do this in Hash table, but that doesn’t meet the requirement ” implement it without using extra memory”

So, Hash table is not a best answer.

I read that operation about bit manipulation last night and that is a fact I found:

“Two same integers after XOR operation, the value is 0, and 0 XOR any integer is the integer itself”

So the condition is that “every element appears twice except for one”

So just do XOR for every element in the array, the final result is the integer we are looking for.