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;
	}