Bits

Problem Question: Reverse a string in C using as little additional memory as possible. Solution Answer: The first solution needs the size of a char and size of two integers, all of which will be allocated from the stack. This solution is the most commonly accepted “good” solution. Here is the code. Method 1 - Using 2 pointer technique We have already seen Reverse String Problem#Method 1 - Iterative in-place using Two Pointers ...

Problem Generate All Strings of n bits, consider A[0..n-1] is an array of size n. Examples Example 1 n = 3 Output: [0, 0, 0] [1, 0, 0] [0, 1, 0] [1, 1, 0] [0, 0, 1] [1, 0, 1] [0, 1, 1] [1, 1, 1] ...

Problem The complement of an integer is the integer you get when you flip all the 0’s to 1’s and all the 1’s to 0’s in its binary representation. For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2. Given an integer num, return its complement. Examples Example 1: Input: num = 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. ...

Problem Given an integer num, return the number of steps to reduce it to zero. In one step, if the current number is even, you have to divide it by 2, otherwise, you have to subtract 1 from it. Examples Example 1: Input: num = 14 Output: 6 Explanation: Step 1) 14 is even; divide by 2 and obtain 7. Step 2) 7 is odd; subtract 1 and obtain 6. Step 3) 6 is even; divide by 2 and obtain 3. Step 4) 3 is odd; subtract 1 and obtain 2. Step 5) 2 is even; divide by 2 and obtain 1. Step 6) 1 is odd; subtract 1 and obtain 0. ...

What x & (-x) returns the rightmost 1 in binary representation of x. -x is the two’s complement of x. -x will be equal to one’s complement of x plus 1. Therefore (-x) will have all the bits flipped that are on the left of the rightmost 1 in x. So x & (-x) will return rightmost 1. x = 10 = 0b1010 (-x) = -10 = 0b0110 x & (-x) = 0b1010 & 0110 = 0010 ...

Problem You are given two numbers A and B. Write a function to determine the number of bits need to be flipped to convert integer A to integer B. OR A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0. For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc. Given two integers start and goal, return the minimum number of bit flips to convert start to goal. ...

Problem Implement an algorithm to determine if a string has all unique characters. Solution Method 1 - Brute Force - Compare All Characters Brute force way can be we take each character in the string and compare it to every other character in the string. We do this using for loops. This would mean a time complexity of O(n^2) because of the nested loop. ...

Problem Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation. Examples Example 1: Input: number = 3 Output: 5 Explanation: Next higher number for 3 is 5. i.e. (00000011 => 00000101). Likewise next lower number of 5 is 3. ...

Problem You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j). Examples Example 1: Input: n = 1024, m = 21, i = 2, j = 6 Output: 1108 Explanation: n's binary representation: 10000000000 m's binary representation: 10101 output's bin represention: 10001010100 i = 2, j = 6 n = 1000| - - - - - | 00 ^ ^ 6 2 n'= 1000| 1 0 1 0 1 | 00 ...

Problem Write a program to swap odd and even bits in an integer with as few instructions as possible (e.g., bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc). Input : An integer x Output : An integer y, which odd and even bit swapped (with 0th bit being least significant bit) Examples Example 1: Input: x = 10 = 1010 Output: 5 = 0101 (0th bit and 1st bit have been swapped,also 2nd and 3rd bit have been swapped) ...