## Bit Manipulation Interview Questions

- 1of 1 vote
A gaming application assigns a sessionid to each player every time they start a new session. These sessionid are all unique and can be selected from 1 to 10^6 numbers. A get() and put() function is used to assign and then release the sessionid for each user. A released session id can then be reused and assigned to another player. How can you write the get() and put() function to handle this in time and space optimized manner?

I did provide o(n) solution with hash table but he seemed to be asking for a bit manipulation or bit masking technique for 32 bit address.

- 0of 0 votes
You are given a positive integer number and you have to return the greatest smaller tidy number of this input number. If the input number itself is tidy, then, it become the answer

Example

Input: 1234

output: 1234

input: 100

output: 99

input 143456

output: 139999.

PS.A tidy number is a number whose digits are in non-decreasing order.

- 0of 0 votes
You are given a positive integer number and you have to return a boolean telling whether the input number is a tidy number or not. A tidy number is a number whose digits are in non-decreasing order. For example, 1234 is a tidy number, 122334 is also a tidy number but 143567 is not a tidy number.

- 0of 0 votes
You are given an integer, print its 4th least significant bit

- 0of 0 votes
Look at the following sequence:

3, 5, 6, 9, 10, 12, 17, 18, 20....

All the numbers in the series has exactly 2 bits set in their binary representation. Your task is simple, you have to find the Nth number of this sequence.

1 <= T <= 10^6

1 <= N <= 10^14

I tried to implement it as follows but it is giving me wrong answer for some hidden cases.`#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; #define MAX 10000 #define MOD 1000000007 long long int m[MAX+1]; long long int sum; long long int binary_search(long long int n) { long long int low=0,high=MAX,mid; while(low<high) { mid=low+(high-low+1)/2; if(m[mid]<=n) low=mid; else high=mid-1; } return low; } int main() { m[0]=1; for(long long int i=1;i<=MAX;i++) m[i]=m[i-1]+i; long long int n,k,l; int t; scanf("%d",&t); for(int test=0;test<t;test++) { scanf("%lld",&n); k=binary_search(n); //cout<<m[k]<<" "; l=n-m[k]; cout<<((1<<k+1)%MOD+(1<<l)%MOD)%MOD<<"\n"; } return 0; }`

- 0of 0 votes
Write a basic function that returns the starting bit position of a 32 bit pattern (i.e. 0xFE6B2840) within a provided byte array.

For example: Input 1 = [ 0x00 0x01 0xFE 0x6b 0x28 0x40 0x02 0x03 ....]

< Starting position is here at bit 16

Result 1 = 16

Note: The bit pattern could be non-byte aligned.

Input 2 = [ 0x00 0x03 0xFC 0xD6 0x50 0x80 0x04 0x06]

< Starting position is bit 15

Result 2 = 15`int bitPosition32bitPattern(char* byteArray, int length)`

- 0of 0 votes
The 64-bit representation of a 48-bit address is said to be in canonical form if bits 63 through 48 are either all ones or all zeroes. Implement X86IsCanonicalAddress().

- 0of 0 votes
Implement a function, set_bit_l_to_r(x,y,l,r).

For bits l to r (both inclusive), if they are set in x, also set them in y. Do not change bits of y, if they are not in range l to r, or those bits are not set in x. l and r are 0-based.

- 0of 0 votes
Define and implement a function that takes two binary numbers represented as strings and returns their sum as another binary number which is again represented as a string. The result should not have any leading zeroes. In case the result is zero, it should be the string "0". Test input "111 1"

- 3of 3 votes
Check if two integers are equal without using any comparison operators.

- 2of 2 votes
Find the number of bits set in a given character array.

After giving him a bit wise operation that was O(n) where n is the number of bits set, he wanted a more optimum solution

- 1of 1 vote
You are given a monochrome bitmap as a byte array (together with its width and height). Draw a horizontal line.

- 0of 0 votes
Check if an integer is a power of 2 or not.

- 1of 1 vote
what does this code do?

`unsigned mystery(unsigned x) { unsigned i=0; while(x) { x=x&(x-1); i++; } return i; }`

- 0of 2 votes
Design a system like friend's functionality in facebook. should have all features of facebook's friends functionality. like for each person , he can have any number of friends , he will get suggestions for new firends , showing common friends if we visits any other profile . algo should be scalable , robust .

- 0of 0 votes
Design a phone book such that fields are searchable with name , with number. Later enhanced teh question asking searchable with address as well.

- 2of 6 votes
Consider the statement

result = a ? b : c;

Implement the above statement without using any conditional statements.

- 1of 1 vote
Write a piece of code to find out if the system is x86 architecure of Sparc

- 0of 0 votes
Write a piece of code to find out if the system is x86 architecture of Sparc

- 0of 0 votes
Write a piece of code to find out if a system is x86 architecture or Sparc?

- 2of 2 votes
Generate MAX_INT (Max signed int value) using bitwise operators. Should work in 32 and 64 bit processors

- 2of 2 votes
You have two numbers decomposed in binary representation, write a function that sums them and returns the result.

Input: 100011, 100100

Output: 1000111

- 0of 2 votes
Implement your own sizeof operator using bitwise operation .

- 3of 3 votes
Given an int, write code to return the number of bits that are 1 in O(m) time, where m is the number of bits that are 1.

- 5of 5 votes
Initially there is a number n written on board. Two players start playing a game turn by turn. Each player has to replace the number n written on the board by n-2^k (for some k >= 0 such that 2^k < n)?

Also the number n-2^k has to be as beautiful as n (The beauty of a number depends on the number of one's in its binary representation). The player loses the game when he can't select any such k.

Given the initial number n, determine which player will win the game if both players play optimally. n > 0 and n <= 10^9.

- 1of 1 vote
Consider 3 32-bit (4 byte) numbers A, B and C

A: A3 A2 A1 A0

B: B3 B2 B1 B0

C: C3 C2 C1 C0

Modify C such that

C0=(A0+B0)/2

C1=(A1+B1)/2

C2=(A2+B2)/2

C3=(A3+B3)/2

Without using the obvious method of masking out each byte of A and corresponding byte of B, and add them, and then right-shifting once. Any other masking is allowed.

- -5of 7 votes
need to implement a weather report functionality. user will provide the city name , need to return the weather report.

if weather station exists n functioning properly , will return the weather report of that station .

else ,

will return the nearest available weather station report.

interviewer looking for optimized manner.

looking for datastructures to stores the cities n algo to return the report.

- 0of 0 votes
Design a Tic Tac Toe Game. Classes Segregation and Code Flow.

- 0of 0 votes
Implement memcpy function which accepts num of bits as argument as oppose to number of bytes.

memcpy (src, dst, num_bits)

- 0of 2 votes
A log file which has user details(user ID,timestamp) and pages visited in a particular day by that user.The next day -the same kind of log file gets generated.How do you find the probability of users who logged in consecutive days out of the second day - logged in users? The question is simple,but they look for the efficient data structure and time complexity.