Skip to content
DevGod Repo
Blog

Bit_Manipulation

3 posts with the tag “Bit_Manipulation”

Leetcode 191: Number of 1 Bits

DevGod
DevGod
Elf Vtuber

Question

In this leetcode problem, we are given a 32 bit integer which we must find the hamming weight of. The hamming weight is the amount of ones present in the binary representation of the given integer. Lastly, the binary representation of a number is basically using zeros and ones to symbolize the number. Our goal is to return this hamming weight of the given integer n.

Solved

To solve this question, we can use bitwise operators and a while loop to optimally find the amount of ones / ON bits. Our while loop continuously runs until given integer n is zero. Each iteration, add the &1 of n to our current sum. The &1 operation adds a 1 to our sum, if the least significant bit inside of n is also set. Also during each iteration, our n integer is bitwise shifted to the right by 1. This has the same affect as dividing n by two before flooring. In terms of binary representation, this shift to the right physically shifts all numbers to the right by one. The last digit after running this operation simply disappears. Once my while loop finishes executing, I use my sum variable to return the answer.

TLDR

Used bitwise operators and a while loop to efficiently iterate through each binary digit of the given n integer. While iterating through my while loop, I add to my sum variable before returning the answer.

Leetcode 2275: Largest Combination With Bitwise AND Greater Than Zero

DevGod
DevGod
Elf Vtuber

About

This problem focuses on finding combinations of numbers from the given array such that the bitwise & AND of all numbers are greater than or equal to 1. Out of all combinations of elements, we return the size of the largest possible combination length.

For example, [1,2,3,4,5] = 3, since the greatest combination length possible would be 1,3,5. This is because 1&3&5 is equal to 1.

Thoughts

An important thing to note about using the bitwise AND & operator is that between two numbers, only the ON (1) bits locations can stay one when performing the AND & bitwise operation. For example, 1 AND 2 would equal zero since they do not share any ON (1) bit locations, but 1 AND 3 would equal 1 since both 1 and 3 have the 1 bit turned on.

  1. 1 = 01, 2 = 10, 01 & 10 = 00
  2. 1 = 01, 3 = 11, 01 & 11 = 01

With this property noted, we can say that for a combination of numbers bitwise AND together have to share ON (1) bit locations among all of them to be greater than zero. In other words, as soon as we reach a number with a bit location that is off, said bit location in the ending result is also turned off.

Seeing this, I decided an optimal way to organize these array elements into valid combinations would be using a hashmap data structure. A hashmap can assign elements into groups based on what bit locations they have flipped on. All elements in a group are in common, as they would all share a specific ON (1) bit location.

Implementation

To solve this problem, I used the built-in Javascript Map() object to record the frequencies of elements in the array that share a specific bit location. To update both myMap and the answer variable, I created a function named “nya” on each candidate in the candidates’ array. The function nya can check each ON(1) bit location a candidate has and update the frequency of that bitmask location if it is on. Lastly, nya can update my ans variable with the maximal length of a valid combination.

For example, for test case [1,2,3,4,5], these are all my valid combinations. To save on memory space, I can update the frequency at a given bit location key instead of maintaining an array of elements at that key. In other words, sorting into buckets, but instead, I keep track of the buckets’ lengths.

  1. [1,3,5] = 3
  2. [2,3] = 2
  3. [4,5] = 2

ans = 3

Closing Thoughts

This is a pretty fun bitwise & hashmap combo problem. While coding this solution, I almost did not go with a frequency map, but instead went with keeping track of all elements in an array inside of the hashmap. Switching to keeping track of the frequency of all elements that shared an ON bit location instead of all the elements in that combo saved my bacon for sure time complexity and memory space-wise.

Leetcode 3011: Find if Array Can Be Sorted

DevGod
DevGod
Elf Vtuber

About

There are two main parts to this problem. First, we need to be able to preform a sort on the array of values. Second, we must evaluate whether two elements in the array need to be swapped, and whether they are swappable given their count of on (1) in their binary representation of themselves. If the given array is already sorted, we can return true. If the given array is unsorted, then we must return whether it can become sorted by swapping elements when their bit counts are equal to each other. Returning false means that we have reached a point where the array is unsorted, and elements are different bit counts from each other, meaning it’s impossible to complete the swap operation.

For example:

  1. [1,5,2] = false, 5 and 2 can’t be swapped, even though they need to be swapped
  2. [1,2,3,4,5] = true, sure some numbers can’t be swapped, but since its already sorted we don’t need to worry

Thoughts

Since this is a bitwise problem, a while loop can find the number of on (1) bits a number has. Also, an ideal sorting algorithm to use would be bubble sort, since the problem specifies you are preforming swaps between elements. Since the main idea is to test for bit counts and whether elements in the array are less than each other, bubble sort is the first thing that popped into my head. With bubble sort, I could check how elements values differ from each other, as well as how their bit counts differ from each other.

Implementation

For my solution I went with a bubble sort approach, since bubble sort is well known for being a sort algorithm that preforms a bunch of swaps between a left and right pointer. By using a bubble sort to implement a solution, I could also include a check during swaps to check if the two elements I’m swapping at the time are different bit counts. If at any point they are different bit counts and need to be swapped, I can simply exit early and return false. Otherwise, I continue on with my business until the array is fully sorted and return true.

For finding the bit count of on (1) bits of a number, I simply use a while loop that counts the & of each first bit. Then to iterate down, I just do an arithmetic shift right, >> 1, to effectively half and floor the number each iteration until the number I am checking reaches zero.

Closing Thoughts

After rereading the question, I noticed that leetcode did specify that only two ADJACENT elements can be swapped in one operation. While my solution passes all test cases, my solution does technically break the only ADJACENT elements rule. https://www.geeksforgeeks.org/bubble-sort-algorithms-by-using-javascript/ The bubble sort algorithm template on geeksforgeeks actually follows this rule a bit better, but at the end of the day still gets the job done :p