Posts published in “Bit”

花花酱 LeetCode 191. Number of 1 Bits

By zxi on November 28, 2021

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Constraints:

The input must be a binary string of length 32.

Follow up: If this function is called many times, how would you optimize it?

Solution: Bit Operation

Use n & 1 to get the lowest bit of n.
Use n >>= 1 to right shift n for 1 bit, e.g. removing the last bit.

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int hammingWeight(uint32_t n) {

int ans = 0;

while (n) {

ans += n & 1;

n >>= 1;

}

return ans;

}

};

花花酱 LeetCode 137. Single Number II

By zxi on November 27, 2021

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

1 <= nums.length <= 3 * 10⁴
-2³¹ <= nums[i] <= 2³¹ - 1
Each element in nums appears exactly three times except for one element which appears once.

Solution: Bit by bit

Since every number appears three times, the i-th bit must be a factor of 3, if not, that bit belongs to the single number.

Time complexity: O(32n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int singleNumber(vector<int>& nums) {

int ans = 0;

for (int s = 0; s < 32; ++s) {

int mask = 1 << s;

int sum = 0;

for (int x : nums)

if (x & mask) ++sum;

if (sum % 3) ans |= mask;

}

return ans;

}

};

花花酱 LeetCode 136. Single Number

By zxi on November 27, 2021

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

Constraints:

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
Each element in the array appears twice except for one element which appears only once.

Solution: XOR

single_number ^ a ^ b ^ c ^ … ^ a ^ b ^ c … = single_number

Time complexity: O(n)
Space complexity: O(1)

C++

class Solution {

public:

int singleNumber(vector<int>& nums) {

int ans = 0;

for (int x : nums)

ans ^= x;

return ans;

}

};

花花酱 LeetCode 29. Divide Two Integers

By zxi on November 26, 2021

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: [−2³¹, 2³¹ − 1]. For this problem, if the quotient is strictly greater than 2³¹ - 1, then return 2³¹ - 1, and if the quotient is strictly less than -2³¹, then return -2³¹.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Example 3:

Input: dividend = 0, divisor = 1
Output: 0

Example 4:

Input: dividend = 1, divisor = 1
Output: 1

Constraints:

-2³¹ <= dividend, divisor <= 2³¹ - 1
divisor != 0

Solution: Binary / Bit Operation

The answer can be represented in binary format.

a / b = c
a >= b * Σ(d_i*2ⁱ)
c = Σ(d_i*2ⁱ)

e.g. 1: 10 / 3
=> 10 >= 3*(2¹ + 2⁰) = 3 * (2 + 1) = 9
ans = 2¹ + 2⁰ = 3

e.g. 2: 100 / 7
=> 100 >= 7*(2³ + 2²+2¹) = 7 * (8 + 4 + 2) = 7 * 14 = 98
ans = 2³+2²+2¹=8+4+2=14

Time complexity: O(32)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int divide(int A, int B) {

if (B == INT_MIN)

return A == INT_MIN ? 1 : 0;

if (A == INT_MIN) {

if (B == -1) return INT_MAX;

return B > 0 ? divide(A + B, B) - 1 : divide(A - B, B) + 1;

}

int a = abs(A);

int b = abs(B);

int ans = 0;

for (int x = 31; x >= 0; --x)

if (a >> x >= b)

ans += 1 << x, a -= b << x;

return (A > 0) == (B > 0) ? ans : -ans;

}

};

花花酱 LeetCode 1863. Sum of All Subset XOR Totals

By zxi on August 4, 2021

The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1.

Given an array nums, return the sum of all XOR totals for every subset of nums.

Note: Subsets with the same elements should be counted multiple times.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b.

Example 1:

Input: nums = [1,3]
Output: 6
Explanation: The 4 subsets of [1,3] are:
- The empty subset has an XOR total of 0.
- [1] has an XOR total of 1.
- [3] has an XOR total of 3.
- [1,3] has an XOR total of 1 XOR 3 = 2.
0 + 1 + 3 + 2 = 6

Example 2:

Input: nums = [5,1,6]
Output: 28
Explanation: The 8 subsets of [5,1,6] are:
- The empty subset has an XOR total of 0.
- [5] has an XOR total of 5.
- [1] has an XOR total of 1.
- [6] has an XOR total of 6.
- [5,1] has an XOR total of 5 XOR 1 = 4.
- [5,6] has an XOR total of 5 XOR 6 = 3.
- [1,6] has an XOR total of 1 XOR 6 = 7.
- [5,1,6] has an XOR total of 5 XOR 1 XOR 6 = 2.
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

Example 3:

Input: nums = [3,4,5,6,7,8]
Output: 480
Explanation: The sum of all XOR totals for every subset is 480.

Constraints:

1 <= nums.length <= 12
1 <= nums[i] <= 20

Solution 1: Brute Force

Use an array A to store all the xor subsets, for a given number x
A = A + [x ^ a for a in A]

Time complexity: O(2ⁿ)
Space complexity: O(2ⁿ)

Python3

# Author: Huahua

class Solution:

def subsetXORSum(self, nums: List[int]) -> int:

xors = [0]

for x in nums:

xors += [xor ^ x for xor in xors]

return sum(xors)

Posts published in “Bit”

花花酱 LeetCode 191. Number of 1 Bits

Solution: Bit Operation

C++

花花酱 LeetCode 137. Single Number II

Solution: Bit by bit

C++

Related Problems

花花酱 LeetCode 136. Single Number

Solution: XOR

C++

Related Problems

花花酱 LeetCode 29. Divide Two Integers

Solution: Binary / Bit Operation

C++

花花酱 LeetCode 1863. Sum of All Subset XOR Totals

Solution 1: Brute Force

Python3