Integer logarithm with base 2

[AleaIactaEst]

Hi,

I'm currently working on a template class which basically works just like the int type, but stores the (signed) integers in their binary representation using size bits, where size is the template parameter of type int.

#include <bitset>
using std::bitset

template <int size>
class varInt {
	private:
		bitset<size> number;
	public:
		//[...]
		
		varInt<size>& operator*=(const varInt<size>& p);
}

I'm stuck at the multiplication at the moment. I got two ideas how to implement the multiplication which i want to compare regarding execution speed.

So what i want to do is to create a bitset of size ilog2(size-2)+1 for the carry bit(s) (well, it's more like a binary carry number).

This approach does not work of course:

#include <cmath>

//[...]

template <int size>
varInt<size>& varInt<size>::operator*=(const varInt<size>& p) {
	bitset< ((int)log(size-2)/log(2)) + 1 > carry;

	//[...]
}

Is there any way to make the preprocessor calculate ilog2(x) or the number of leading zeros of x?

[R0mai]

You can use template meta programming to calculate it. It is resolved at compile time, so you can use them as template parameters.

For general info : http://en.wikipedia.org/wiki/Template_metaprogramming
You might get some nice help from boost::mpl : http://www.boost.org/doc/libs/1_51_0/libs/mpl/doc/index.html

Preprocessor is not capable of such calculations because the preprocessor is not Turing complete as opposed to templates.

[AleaIactaEst]

Thanks for your quick answer.

I tried to solve the problem with template meta programming as it is described in the wiki article, but i can't get the following to work:

//Round down to greatest power of two which is less than or equal to x
template <int x>
struct flp2l {
	enum { value = [...] };
};

//Calculate integer logarithm with base 2 of x
template <int x>
struct ilog2 {
	enum { value = ( !((x)&(x-1)) ? (1+ilog2<x/2>::value) : (ilog2<flp2l<x>::value > ::value) )
		 };
};

template <>
struct ilog2<1> {
	enum { value = 0 };
};

Note: !((x)&(x-1)) is true if x is a power of 2, false otherwise

flp2l works nicely, but when i tried to calculate ilog<2>::value i get the following error message:

error: incomplete type ‘ilog2<2>’ used in nested name specifier

This problem is caused by the (ilog2<flp2l<x>::value>::value) part of the code, but i cannot find a way to solve it.

I want to avoid the following solution, because in this case the compiler creates a lot of template instances of the ilog2 struct if x is close to 2^n-1 for an integer n.

//Calculate integer logarithm with base 2 of x
template <int x>
struct ilog2 {
	enum { value = ( !((x)&(x-1)) ? (1+ilog2<x/2>::value) : (ilog2<x-1>::value) )
		 };
};

[R0mai]

Here I found some simple algorithms for this :
http://my.safaribooksonline.com/book/information-technology-and-software-development/0201914654/power-of-2-boundaries/ch03lev1sec2

For example branch free solution :

unsigned flp2(unsigned x) {
   x = x | (x >> 1); 
   x = x | (x >> 2); 
   x = x | (x >> 4); 
   x = x | (x >> 8); 
   x = x | (x >>16); 
   return x - (x >> 1); 
}

This can be easily implemented in templates :)

(Be careful about sizeof(unsigned))

[AleaIactaEst]

I did use this algorithm for implementation of the struct flp2l and it works nicely :)

However that's not my problem at the moment. I've explained that in a bit confusing way i must admit.

The problem is, that the c++ compiler somehow does not like nested template parameters in struct ilog2, and i can't find a solution to this problem. I don't even understand what the compiler is trying to tell me.

[R0mai]

I think you're over complicating it with that branch and flp2.
This works nicely :

template <int x>
struct ilog2 {
	enum { value = (1 + ilog2<x/2>::value) };
		 
};

template <>
struct ilog2<1> {
	enum { value = 0 };
};

I have to admit, I've no clue what was the problem with your previous code :(

[AleaIactaEst]

Oh you're right. That's a nice and simple solution :)

Problem solved, thanks !