CC150 5.3

5_3.cpp

/* CC150 5.3
 * Given a positive integer, print the next smallest and the next largest number that have the same number of
 * 1 bits in their binary representation.
 */

#include <iostream>

using namespace std;

unsigned int reverse(unsigned int num, int k); // reverse from LSB through the kth bit, k < BIT_SIZE

// Lexicographic order: http://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
unsigned int nextLargestCplx(unsigned int num) // return the next largest number that have the same number of 1 bits
{
	if (!num) // zero does not contain 1's
		return 0;
	int k = 1; // find the least significant "0" followed by a "1"
	while (k !=32 && num & (1 << k) || !(num & (1 << (k - 1)))) // current bit is "1" or is "0" but followed by "0"
		++k;
	if (k == 32) // current number is the largest
		return 0;
	num ^= (1 << k); // swap bit k
	int l = 0; // find the least significant "1" on the right of bit k
	while (l < k && !(num & (1 << l))) // current bit is "0" and is on the right of bit k
		++l;
	num ^= (1 << l); // swap bit l
	return reverse(num, k - 1); // reverse the sequence on the right of bit k
}

unsigned int nextLargest(unsigned int num) // return the next largest number that have the same number of 1 bits
{
	if (!num)
		return 0;
	int k = 1;
	while (k != 32 && num & (1 << k) || !(num & (1 << (k - 1))))
		++k;
	if (k == 32)
		return 0;
	num ^= (1 << k);
	int l = 0;
	while (l < k && !(num & (1 << l)))
		++l;
	return num & (~0 << k) | ((1 << (k - l - 1)) - 1); // shift the tailing sequence instead of reversing
}

unsigned int nextSmallest(unsigned int num) // return the next smallest number that have the same number of 1 bits
{
	unsigned int temp = nextLargest(~num);
	if (temp)
		return ~temp;
	else
		return 0;
}

unsigned int getNext(unsigned int n) // arithmetic approach to get next number
{
	unsigned int c = n; // 32 bits
	int c0 = 0, c1 = 0;
	while ((c & 1) == 0 && c) { // count tailing zeros
		++c0;
		c >>= 1;
	}
	while ((c & 1) == 1) { // count 1's immediately following tailing zeros
		++c1;
		c >>= 1;
	}
	if (c0 + c1 == 32 || c0 + c1 == 0) // current number is the largest or is zero
		return 0;
	return n + (1 << c0) + (1 << (c1 - 1)) - 1;
}

unsigned int getPrev(unsigned int n) // arithmetic approach to get previous number
{
	unsigned int c = n; // 32 bits
	int c0 = 0, c1 = 0;
	while ((c & 1) == 1) { // count tailing ones
		++c1;
		c >>= 1;
	}
	if (!c) // current number is the smallest
		return 0;
	while ((c & 1) == 0 && c) { //  // count zeros immediately following tailing ones
		++c0;
		c >>= 1;
	}
	return n - (1 << c1) - (1 << (c0 - 1)) + 1;
}

// Reverse bits the obvious way: https://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
unsigned int reverse(unsigned int num, int k) // reverse from LSB through the kth bit, k < BIT_SIZE
{
	int mask = (~0 << (k + 1)); // mask of the bits to be reversed, e.g.11111000
	unsigned int result = num & mask; // copy the unchanged bits
	unsigned int rev = num;
	int count = 0;
	while (count++ != k) { // reverse the sub-sequence
		num >>= 1;
		rev <<= 1;
		rev |= num & 1;
	}
	return result | (rev & ~mask); // append to the original sequence
}

// Hamming weight: http://en.wikipedia.org/wiki/Hamming_weight
// better when most bits in x are 0
// if x originally had n bits that are 1, then after n iterations x will be reduced to zero.
// use 3 arithmatic operations and one comparison per "1" bit in x
int popCount(unsigned int x) // return the number of 1 bits
{
	int count;
	for (count = 0; x; ++count)
		x &= x - 1;
	return count;
}

int main()
{
	unsigned int num;
	cin >> num;
	cout << "Number of 1's: " << popCount(num) << endl;
	cout << "Next largest: " << nextLargest(num) << endl;
	cout << "Arithmetic next: " << getNext(num) << endl;
	//	cout << "Number of 1's: " << popCount(nextLargest(num)) << endl;
	cout << "Next Smallest: " << nextSmallest(num) << endl;
	cout << "Arithmetic prev: " << getPrev(num) << endl;
	//	cout << "Number of 1's: " << popCount(nextSmallest(num)) << endl;
	return 0;
}

5_3_clear.cpp

/* CC150 5.3
 * Given a positive integer, print the next smallest and the next largest number that have the same number of
 * 1 bits in their binary representation.
 */

#include <iostream>

using namespace std;

unsigned int nextLargest(unsigned int num) // return the next largest number that have the same number of 1 bits
{
	if (!num)
		return 0;
	int k = 1;
	while (k != 32 && num & (1 << k) || !(num & (1 << (k - 1))))
		++k;
	if (k == 32)
		return 0;
	num ^= (1 << k);
	int l = 0;
	while (l < k && !(num & (1 << l)))
		++l;
	return num & (~0 << k) | ((1 << (k - l - 1)) - 1); // shift the tailing sequence instead of reversing
}

unsigned int nextSmallest(unsigned int num) // return the next smallest number that have the same number of 1 bits
{
	unsigned int temp = nextLargest(~num);
	if (temp)
		return ~temp;
	else
		return 0;
}

unsigned int getNext(unsigned int n) // arithmetic approach to get next number
{
	unsigned int c = n; // 32 bits
	int c0 = 0, c1 = 0;
	while ((c & 1) == 0 && c) { // count tailing zeros
		++c0;
		c >>= 1;
	}
	while ((c & 1) == 1) { // count 1's immediately following tailing zeros
		++c1;
		c >>= 1;
	}
	if (c0 + c1 == 32 || c0 + c1 == 0) // current number is the largest or is zero
		return 0;
	return n + (1 << c0) + (1 << (c1 - 1)) - 1;
}

unsigned int getPrev(unsigned int n) // arithmetic approach to get previous number
{
	unsigned int c = n; // 32 bits
	int c0 = 0, c1 = 0;
	while ((c & 1) == 1) { // count tailing ones
		++c1;
		c >>= 1;
	}
	if (!c) // current number is the smallest
		return 0;
	while ((c & 1) == 0 && c) { //  // count zeros immediately following tailing ones
		++c0;
		c >>= 1;
	}
	return n - (1 << c1) - (1 << (c0 - 1)) + 1;
}

int main()
{
	unsigned int num;
	cin >> num;
	cout << "Next largest: " << nextLargest(num) << endl;
	cout << "Arithmetic next: " << getNext(num) << endl;
	cout << "Next Smallest: " << nextSmallest(num) << endl;
	cout << "Arithmetic prev: " << getPrev(num) << endl;
	return 0;
}