how to implement sum of bits using template metaprogramming

[andrey.vul]

I'm tryin to convert this:
long sumOfBits(int n) {
long x = 0;
int i;
for (i = n - 1; i >= 0; i--)
x += (1 << i);
return x;
}

into something like this:
template <int n> struct sumOfBits {
static const unsigned char u8value = (unsigned char)((1 << n) +
sumOfBits<n - 1>::u8value);
static const unsigned __int16 u16value = (unsigned __int16)((1 << n)
+ sumOfBits<n - 1>::u16value);
static const unsigned __int32 u32value = (unsigned __int32)((1 << n)
+ sumOfBits<n - 1>::u32value);
static const unsigned __int64 u64value = (unsigned __int64)((1 << n)
+ sumOfBits<n - 1>::u64value);
};
template <> struct sumOfBits <0> {
static const unsigned char u8value = (unsigned char)1;
static const unsigned __int16 u16value = (unsigned __int16)1;
static const unsigned __int32 u32value = (unsigned __int32)1;
static const unsigned __int64 u64value = (unsigned __int64)1;
};

and so far, all expansions, that have multiples of 8 (8, 16, 32, 64)
return 0 due to overflow.
Any way to correctly rewrite the template?

 

[Alf P. Steinbach]

* (e-mail address removed):

I'm tryin to convert this:
long sumOfBits(int n) {
long x = 0;
int i;
for (i = n - 1; i >= 0; i--)
x += (1 << i);
return x;
}

into something like this:
template <int n> struct sumOfBits {
static const unsigned char u8value = (unsigned char)((1 << n) +
sumOfBits<n - 1>::u8value);
static const unsigned __int16 u16value = (unsigned __int16)((1 << n)
+ sumOfBits<n - 1>::u16value);
static const unsigned __int32 u32value = (unsigned __int32)((1 << n)
+ sumOfBits<n - 1>::u32value);
static const unsigned __int64 u64value = (unsigned __int64)((1 << n)
+ sumOfBits<n - 1>::u64value);
};
template <> struct sumOfBits <0> {
static const unsigned char u8value = (unsigned char)1;
static const unsigned __int16 u16value = (unsigned __int16)1;
static const unsigned __int32 u32value = (unsigned __int32)1;
static const unsigned __int64 u64value = (unsigned __int64)1;
};

and so far, all expansions, that have multiples of 8 (8, 16, 32, 64)
return 0 due to overflow.
Any way to correctly rewrite the template?

Off the cuff, to reproduce the behavior of the original non-tempalte
function:

template< int n >
struct SumOfBits
{
enum{ value = (1L << (n-1)) | ((1L << (n-1)) - 1) };
};


Cheers, & hth.,

- Alf

 

[Victor Bazarov]

* (e-mail address removed):

Off the cuff, to reproduce the behavior of the original non-tempalte
function:

template< int n >
struct SumOfBits
{
enum{ value = (1L << (n-1)) | ((1L << (n-1)) - 1) };
};

I believe you meant

template< unsigned n > struct SumOfBits
{
enum{ value = (1L << (n - 1)) + SumOfBits<n-1>::value };
};

template<> struct SumOfBits<1>
{
enum { value = 1 };
};

template<> struct SumOfBits<0>
{
enum { value = 0 };
};

You need recursion in templates to emulate the loop.

V

 

[Victor Bazarov]

* (e-mail address removed):

Off the cuff, to reproduce the behavior of the original non-tempalte
function:

template< int n >
struct SumOfBits
{
enum{ value = (1L << (n-1)) | ((1L << (n-1)) - 1) };
};

Well, the loop is uncalled for, so you're, right, it could just be

template<unsigned n>
struct SumOfBits
{
enum { value = (1 << n) - 1 }; // no need to OR anything
};

V

 

[Alf P. Steinbach]

* Victor Bazarov:

Well, the loop is uncalled for, so you're, right, it could just be

template<unsigned n>
struct SumOfBits
{
enum { value = (1 << n) - 1 }; // no need to OR anything
};

I believe this latter version has Undefined Behavior in the case of n =
number of bits in int. Also, the original functions had long result.

Cheers,

- Alf

 

[Victor Bazarov]

* Victor Bazarov:

I believe this latter version has Undefined Behavior in the case of n
= number of bits in int.

So did the function the OP wanted converted.

Also, the original functions had long
result.

When an enum is defined the underlying type is picked by the compiler,
you can take control in your hands by doing

template<unsigned n>
struct SumOfBits
{
static long const value = (1L << n) - 1;
};

but I guess 'enum' is a bit more "portable" and hence it was suggested
by you.

V

 

[Alf P. Steinbach]

* Victor Bazarov:

So did the function the OP wanted converted.

Nope, it's quoted at the top.

When an enum is defined the underlying type is picked by the compiler,
you can take control in your hands by doing

template<unsigned n>
struct SumOfBits
{
static long const value = (1L << n) - 1;
};

Yes, the L is a good correction, doing it as in the code I presented.

but I guess 'enum' is a bit more "portable" and hence it was suggested
by you.

enum is more portable and it doesn't require a separate definition
(lacking in this latest version).

Cheers,

- Alf