C++ STL bitset and bitmask: problems

C++ STL Bit Manipulation Problems:

Here is the list of questions based on bit manipulation:

• UVa 00594 - One Little, Two Little ... (manipulate bit string with bitset)
• UVa 00700 - Date Bugs (can be solved with bitset)
• UVa 01241 - Jollybee Tournament (LA 4147, Jakarta08, easy)
• UVa 10264 - The Most Potent Corner * (heavy bitmask manipulation)
• UVa 11173 - Grey Codes (D & C pattern or one liner bit manipulation)
• UVa 11760 - Brother Arif, ... (separate row+col checks; use two bitsets)
• UVa 11926 - Multitasking * (use 1M bitset to check if a slot is free)
• UVa 11933 - Splitting Numbers * (an exercise for bit manipulation)

Here is the link to the problems:

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=626

Here are my solutions and hints to some problems.

Solutions and hints:

Uva 594: One Little, Tow Little, Three Little Endians

There are many solutions to this problem, but I found this one fairly awesome. What happens is that you scan an integer.

An integer is 4 byte in memory. A character is 1 byte in memory.

We store the address of our integer in a character pointer. This makes our integer as an array of character with four elements in it. We know just swap its elements as we need to do.

The swapping here is not usual swapping. You need to grab a pencil and understand how this swapping works.

Being good at pointers is a must to understand this problem.

#define Swap(a, b) a=a^b, b=a^b, a=a^b
	int main(int argc, char const *argv[]) {
	int N;
	while(scanf("%d", &N)==1){
	int reverser = N;
	char* eachByte = (char*)&reverser;
	Swap(eachByte[0], eachByte[3]);
	Swap(eachByte[1], eachByte[2]);
	printf("%d converts to %d\n", N, reverser);
	}
	return 0;
	}

Uva 11926: Multitasking

Declare a bitset with a length of 100000. Just do brute force. Iterating each time, setting ones, and in case, already an element is one, we are at "CONFLICT" case.

Here is the code that does same:

#define maxn 1000005
	int main(int argc, char const *argv[]) {
	int n, m;
	while (scanf("%d %d", &n, &m)==2) {
	if(n==0&m==0)
	break;
	bitset<maxn> b1;
	bool success = true;
	for (size_t i = 0; i < n; i++) {
	int a, b;
	scanf("%d %d", &a, &b);
	for (size_t j = a; (j < b)&&success; j++) {
	if(b1[j]==1){
	success=false;
	}else if(b1[j]==0)
	b1[j]=1;
	}
	}
	for (size_t i = 0; i < m; i++) {
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);
	bool done=false;
	for(int i=a;i<maxn&&success;i+=c){
	int j;
	for (j = i; j < i+b-a&&success; j++) {
	if(j>maxn){
	done=true;
	break;
	}
	if(b1[j]==1){
	success=false;
	}else if(b1[j]==0)
	b1[j]=1;
	}
	if(done)
	break;
	}
	}
	if(success)
	cout<<"NO CONFLICT"<<'\n';
	else
	cout << "CONFLICT" << '\n';
	}
	return 0;
	}

Bits important methods/tricks

Bits important methods/tricks

Here are some important tricks on Bits 

1. To multiply/divide an integer by 2 we need to only shift the bits in the integer left/right respectively/

2. To set/turn-on the j-th item (in 0-based indexing) of the set, we use bitwise OR operation \[S = s |(1<<j)\]

3. To check if the j-th item of the set is on, use the bitwise AND operation T = S&(1<<j). if T=0, it was off, else it was on.

4. TO clear/turn-off j-th item of the set, we use the bitwise AND and NOT operations. 

S = S& (~(1<<j)).

5. To toggle(flip the status of) the j-th item of the set, we use the bitwise XOR operation:

S = S^(1<<j).

6. To get the value of the least significant bit that is on (that is, the first on bit from the right), use 

T = (S&(-S)). Assuming(which is indeed the case) that negative numbers are stored as two's complements.

7. To turn on all bits in a set of size n, we use S = (1<<n)-1

I suggest you pick up a pen/pencil and figure out why these tricks/methods work.

Here are some less commonly used bit manipulation tricks:

1. (Very Important, imagine other way of checking it) Determine if S is a power of two: (111) is not a power of 2, but (100) is a power of 2. You can check it as follows:
                                                                              S&(S-1) == 0

2.  Turn off the first(from right) on bit in S. That is $(101000) -> (100000)$. You can do it as follows:
                                                                              S&(S-1)
3. Turn on the last zero in S. $(101001) -> $101011)$. This can be done as follows:
                                                                               S|(S+1)
4. Turn off the last consecutive run of ones in S. (100111) -> (100000):
                                                                                S&(S+1)
5. Turn on the last consecutive run of zeros in S. (100100)->(100111):
                                                                                S|(S-1)

Bit Manipulation: Some sample questions

Practice Questions on Bit Manipulation.

Given two 32 bit numbers N, M and two-bit positions i, j. Set all the bits between i and j in N equal to M.

• Algorithm:
• Temp = ~0 //(all ones)
• left = temp - ((1<<j)-1) //(1<<j)-1 gives a number with j-1 continuous ones and rest zeros. This //This gives us a number left with all ones except last j-1 zeros.
• right = ((1<<i)-1)//this gives us a number with all zeros except last i-1 ones.
• mask = right|left //all ones except those between the ith and jth position.
• answer = (n&mask)|(m<<i) //n&mask clears all the places between ith and jth position by //placing zeros there. m<<i shifts m by i bits and taking or of these two completes the task.

Given an integer print the next largest number that have the same number of 1 bits in its binary representations.

• Algorithm:
• Traverser from right to left, and once you've passed a one turn the first 0 after it to 1. This makes us our number increase by $2^i$. Example: ******011100 now becomes ******111100.
• Turn the one just right to our current position to zero. Now it is bigger by $2^i - 2^j$ Where j=i-1. Example: ******111100 now becomes ******101100.
• Thus we are now ahead of our original number, but we are too ahead, we need to make this number close to the original number as much as possible. Make the number as small as possible by rearranging all the 1s to be as far right as possible.******101100 now becomes ******100011.

Here is the code:

bool getBit(int n, int index){
	return ((n & (1<<index)) > 0);
	} ///setting the bit what it does is crates a number with one only
	// at that index and all rest zero, and taking and with original gives answer
	int setBit(int n, int index, int to){
	if(to){
	return n|1<<index;
	}else{
	int mask = ~(1<<index);
	return n & mask;
	}
	}//setting bit at a number.
	int getNextLargest(int n){
	if(n<=0)
	return -1; //in casethe number is negative, we return -1 to denote error
	int index = 0;
	int countOnes = 0;
	while(!getBit(n, index)){ //go the location of first one
	index++;
	}
	while(getBit(n, index)){//now go to the location of first zero to left of this one. We keep count of the ones we have travelled
	index++;
	countOnes++;
	}
	n=setBit(n, index, 1); //set the zero we have reached to one
	index--; // decrement to previous location
	n = setBit(n, index, 0); //set this location to one.
	countOnGiven an integer print the next largest number that have the same number of 1 bits in their binary representations. es--; //decrement the number of ones as we have turned off a one in previous step.
	for(int i=index-1;i>=countOnes;i--){ //set all previous locations as zero except first countOnes we'll place ones there.
	n=setBit(n, i, 0);
	}
	for(int i=countOnes-1;i>=0;i--){//set all first countOnes locations as one.
	n = setBit(n, i, 1);
	}
	return n;// done return the number.

Given an integer print the number just smaller than it that have the same number of 1 bit in its binary representations.

The Algorithm is similar. Try to implement it on your own. A slight modification in the previous code will yield an answer to this problem.

• Algorithm:
• Traverser from right to left, and once you've passed a zero-turn the first 1 after it to 0.
• Turn the zero just right to our current position to one.
• Make the number as big as possible by shifting all the ones as far to the left as possible.

For code: A slight modification in getNextLargest will yield the code. Instead of tracking ones now, track for zeros and do the same things. If we were setting a bit to one, set it to zero and vice versa. Try it on your own.

Determine the number of bits required to convert integer A to integer B. Example Input: 31, 14; Output: 2.

This is a simple question, you can figure out which bits in two numbers are different by operation of xor. If a bit in the result is one that means the bits at that place in the numbers were zero.