twin_bits.cpp

template<typename T>
std::size_t find_lsb(T value)
{
	T less = value - 1;

	value = (less | value) ^ less;

	return std::log2(value + 1);
}

template<typename T>
T find_msb(T value)
{
	static const std::size_t max_bit = sizeof(T) * 8;
	
	if (value == 0) throw std::invalid_argument("No bit set at all!");
	
	for (long bit = max_bit - 1; bit >= 0; --bit)
	{
		if (value & (1 << bit)) return bit;
	}
}

template<typename T>
std::size_t cardinality(const T& value, std::size_t msb)
{
	if ((value & (value - 1)) == 0) return 1;

	if ((value & (value + 1)) == 0) return std::log2(value + 1);

	std::size_t count = 1;

	for (std::size_t i = 0; i < msb; ++i)
	{
		if (value & (1 << i)) ++count;
	}

	return count;
}

template<typename T>
std::size_t cardinality(const T& value)
{
	return cardinality(value, find_msb(value));
}

template<typename T>
std::pair<T, T> twins(const T& value)
{
	// Nothing to do here.
	if (value == 0) return {0, 0};

	// If its a power of 2, just left/right shift
	if ((value & (value - 1)) == 0)
	{
		return {value << 1, value >> 1};
	}

	T lsb = find_lsb(value);

	T msb = find_msb(value, lsb);

	T next_largest;

	// We need to differentiate between when a number is
	// a cluster of bits, e.g. 0111, and when it is not,
	// e.g. 01010. If it is a cluster of bits, the
	// solution to find the next-largest value is to
	// left shift the MSB and right shift the non-MSB bits.

	// A value is a cluster of bits when we can right
	// shift the values to the start to remove all 0s
	// before the LSB (11000 -> 00011), then add one
	// and have a power of 2. I.e. if this is a cluster,
	// adding 1 will make it a power of 2. A value is
	// a power of 2 if you can substract 1, AND those
	// two values and get 0. If it is not a cluster of
	// bits, you'll get something like 10110 -> 01011,
	// to remove the 0 padding, then 01100 when adding 1
	// and then the power-of-2 check will fail because
	// 01100 & 01011 is not 0, but 01000 -> thus not a cluster

	T copy = value >> lsb;

	// Is a cluster of bits
	if ((copy & (copy + 1)) == 0)
	{
		// Unset the old MSB, which we want
		// to left shift afterwards
		next_largest = copy & ~(1 << (msb - 1));

		// If we can't right shift the non-msb bits, we
		// already have the next-largest value
		if (lsb > 1) next_largest >>= 1;

		// Add the new, left-shifted MSB
		next_largest |= (1 << msb);

		// If it's a cluster of bits and lsb is at bit 1,
		// there is no smaller value with the same # of bits
		if (lsb == 0) return {value, next_largest};
	}

	else
	{
		// If the value is not composed of a cluster of bits
		// the idea is to find the first gap in the bits
		// and shift the values before the gap to the left

		// We find the first gap in the bits of A = 1001 by
		// (1) adding 1: 1001 + 1 = 1010 -> B
		// (2) ORing those two: 1001 | 1010 = 1011 -> C
		// (3) XORing C with A: 1001 ^ 1011 = 0010
		// (4) Taking the log2 to find the bit position where the gap was.

		T temp = copy | (copy + 1);

		// The gap bit
		std::size_t gap = lsb + std::log2(temp ^ copy);

		// Mask off the bits before the gap
		T before_gap_mask = value & ((1 << gap) - 1);

		// Get the bits after the gap by unsetting the masked bits
		T after_gap = value & ~before_gap_mask;

		next_largest = after_gap | (before_gap_mask << 1);
	}

	T next_smallest = 0;

	// To find the next smallest value, again two cases
	// If the first bit is not set, just shift the LSB one
	// to the right. Else if the first bit is set, we'll have
	// to shift the MSB one to the right and then cram all the
	// non-MSB bits right next to the MSB to get the highest
	// possible value with the MSB being one to the right.

	if (value & 1)
	{
		std::size_t not_msb_bits = cardinality(value, msb) - 1;

		msb -= 1;

		// Add in the new MSB
		next_smallest |= (1 << msb);

		// Create a mask containing bits for all the non-MSB bits
		T mask = (1 << not_msb_bits) - 1;

		// Shift those next to the MSB
		mask <<= (msb - not_msb_bits);

		// Add in the non-MSB bits
		next_smallest |= mask;
	}

	else
	{
		// Unset the old LSB
		next_smallest = value & ~(1 << lsb);

		// Insert the LSB one position before
		next_smallest |= (1 << (lsb - 1));
	}

	return {next_smallest, next_largest};
}