Leetcode-Question-371: Sum of Two Integers

原文链接:
https://leetcode.com/problems/sum-of-two-integers/

题目描述:
371. Sum of Two Integers
Difficulty: Easy

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.

解析:

Leetcode-Question-201: Bitwise AND of Numbers Range

原文链接:
https://leetcode.com/problems/bitwise-and-of-numbers-range/

题目描述:
201. Bitwise AND of Numbers Range
Difficulty: Medium

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

解答:

 

Leetcode-Question-137: Single Number II

原文链接:
https://leetcode.com/problems/single-number-ii/

题目描述:
Single Number II
Difficulty: Medium

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解答:

朴素的模3方法:

牛人解法:

若假设00, 01, 10分别表示某一个bit上有0个,1个,2个1,则状态转移为00->01->10->00

参考https://leetcode.com/discuss/6632/challenge-me-thx这页面下的第二位仁兄的解释:

The code seems tricky and hard to understand at first glance. However, if you consider the problem in Boolean algebra form, everything becomes clear.

What we need to do is to store the number of ‘1’s of every bit. Since each of the 32 bits follow the same rules, we just need to consider 1 bit. We know a number appears 3 times at most, so we need 2 bits to store that. Now we have 4 state, 00, 01, 10 and 11, but we only need 3 of them.

In this solution, 00, 01 and 10 are chosen. Let ‘ones’ represents the first bit, ‘twos’ represents the second bit. Then we need to set rules for ‘ones’ and ‘twos’ so that they act as we hopes. The complete loop is 00->10->01->00(0->1->2->3/0).

  • For ‘ones’, we can get ‘ones = ones ^ A[i]; if (twos == 1) then ones = 0’, that can be tansformed to ‘ones = (ones ^ A[i]) & ~twos’.
  • Similarly, for ‘twos’, we can get ‘twos = twos ^ A[i]; if (ones* == 1) then twos = 0’ and ‘twos = (twos ^ A[i]) & ~ones’. Notice that ‘ones*’ is the value of ‘ones’ after calculation, that is why twos is calculated later.

Detailed State Table