- Published on
BigFrontEnd Category 4 Binary Operations Questions
- Authors
- Name
- Yinhuan Yuan
Introduction
This blog post summarizes the Binary operation questions found on BigFrontEnd.Dev and leetcode.
1.count "1" in binary form
96.https://bigfrontend.dev/problem/how-many-1s-in-binary
Given an integer, count "1" in its binary form.
countOne(1) // 1, "1"
countOne(257799) // 12, "111110111100000111"
If you use built-in string methods in JavaScript, please do understand the time complexity, they are not free. Actually this could be easily done by counting the digit one by one. Could you think of some other approaches?
/**
* @param {number} num - integer
* @return {number} count of 1 bit
*/
function countOne(num) {
return num.toString(2).replace(/0/g, '').length
}
function countOne(num) {
return num.toString(2).replaceAll('0', '').length
}
function countOne(num) {
let ans = 0
while (num > 0) {
num = num & (num - 1)
ans += 1
}
return ans
}
/**
* @param {number} num - integer
* @return {number} count of 1 bit
*/
function countOne(num) {
// Convert the number to a 32-bit unsigned integer
num = num >>> 0
let count = 0
// Check each bit from the most significant to the least significant
for (let i = 31; i >= 0; i--) {
// Check last bit
if ((num & 1) === 1) {
count++
}
// Shift right
num = num >> 1
}
return count
}
2. implement Math.pow()
109.https://bigfrontend.dev/problem/implement-Math-pow
Can you write your own Math.pow() ? The power would only be integers.
pow(1, 2)
// 1
pow(2, 10)
// 1024
pow(4, -1)
// 0.25
All inputs are safe.
Follow-up
You can easily solve this problem by multiplying the base one after another, but it is slow. For power of n, it is needed to do the multiplication n times, can you think of a faster solution ?
/**
* @param {number} base
* @param {number} power - integer
* @return {number}
*/
function pow(base, power) {
const negative = power < 0 ? true : false
power = negative ? -power : power
let ans = 1
let temp = base
while (power > 0) {
// check the last bit is 1 or not
if ((power & 1) === 1) {
// power % 2 === 1
ans = ans * temp
}
temp = temp * temp
power = power >> 1 // power = power // 2
}
return negative ? 1 / ans : ans
}
function pow(base, power) {
const helper = (base, power) => {
if (power === 0) return 1
const ans = helper(base, Math.floor(power / 2))
return power % 2 === 1 ? base * ans * ans : ans * ans
}
return power < 0 ? 1 / helper(base, -power) : helper(base, power)
}
3.find the single integer
162.https://bigfrontend.dev/problem/find-the-single-integer
Given an array of integers, all integers appear twice except one integer, could you quickly target it ?
const arr = [10, 2, 2, 1, 0, 0, 10]
findSingle(arr) // 1
What is time & space cost of your approach ? Could you do better ?
Solution:
Because of 0 ^ a = a, we can choose 0 as the initial value.
function findSingle(arr) {
let ans = 0
arr.forEach((val) => {
ans = ans ^ val
})
return ans
}
4.implement Math.clz32()
172.https://bigfrontend.dev/problem/clz32
Math.clz32() returns the number of leading zero bits in the 32-bit binary representation of a number.
Let's try to implement it by ourselves.
clz32(1) // 31
clz32(10000) // 18
clz32(25.45) // 27
Solution:
Use num & (1 << i) to every bit.
/**
* @param {number} num
* @returns {number}
*/
function clz32(num) {
// Convert the number to a 32-bit unsigned integer
num = num >>> 0
// If the number is 0, all 32 bits are zeros
if (num === 0) {
return 32
}
let count = 0
// Check each bit from the most significant to the least significant
for (let i = 31; i >= 0; i--) {
// (1 << i)
// num & (1 << i)
if ((num & (1 << i)) !== 0) {
break
}
count++
}
return count
}
Solution 2:
Convert it to binary string and counting the leading zeroes.
function clz32(num) {
num = num >>> 0
const s = [...num.toString(2).padStart(32, '0')]
const index = s.findIndex((val) => val === '1')
return index === -1 ? 32 : index
}