Page 1 of 1

byte to bits

Posted: Sat Mar 07, 2009 4:55 pm
by praethorian
Hi all,
I am using this byte2bits function, but I wondering if there is a better/easier way to do that.

Thanks.

Code: Select all

int MyProjectFrame::Byte2Bits(int number){
	int *bits = new int[8];
	int divider = 128;

	for (int i = 0; i<8; i++){
		bits[i] = number / divider;
		number = number % divider;
		divider = divider / 2;
	}

	return bits;
}

Re: byte to bits

Posted: Sat Mar 07, 2009 5:26 pm
by Giles
Just little shorter way to do the same...

Code: Select all

int MyProjectFrame::Byte2Bits(int number){
	int *bits = new int[8];

        for (int i = 7; i >= 0; --i)
        {
	        bits[i] = number & 1;
	        number >>= 1;
        }
	return bits;
}
Or

Code: Select all

int MyProjectFrame::Byte2Bits(int number){
	int *bits = new int[8];

        for (int *CurBit = bits + 8; CurBit > bits;)
        {
	        *--CurBit = number & 1;
	        number >>= 1;
        }
	return bits;
}

Posted: Sun Mar 08, 2009 1:46 am
by computerquip
Don't forget to delete the array.

EDIT: Nevermind, I see that it's returned and very valid. 30 minutes of sleep doesn't work.

Posted: Sun Mar 08, 2009 10:12 am
by orbitcowboy
Here is my way to compute this, its a bit more efficient :-):

Code: Select all


template <unsigned int ui = 8> void vByteToBits(int &number, unsigned short *bits)
{
    bits[ui-1] = number & 1;
    number >>= 1;
    vByteToBits<ui-1>(number,bits);
}
template <> void vByteToBits<0>(int &, unsigned short *){}

unsigned short *usByteToBits(int &number)
{
	unsigned short *bits = new unsigned short[8];	
 	vByteToBits(number,bits);
	return bits;
}

use it like this

Code: Select all

	int i = 12;
	unsigned short *bits = usByteToBits(i);
	std::cout << std::endl;

	for(unsigned int uiIndex = 0; uiIndex < 8; uiIndex++)
	{
		std::cout << bits[uiIndex]  << " ";  
	}
	delete bits;
	std::cout << std::endl;
Regards

Orbitcowboy

Posted: Sun Mar 08, 2009 10:42 am
by Giles
orbitcowboy wrote:Here is my way to compute this, its a bit more efficient :-):
It will really depend on the optimizer. For each array item you get a (almost) recursive call (which is not efficient at all) unless the optimizer is able to inline such a complex template construction. But it may even not compile with some old compilers so I am not sure of the success of the inline in any cases.

You should reserve templates for the cases they bring a real gain. Wisely wxWidgets has avoided their use.

Posted: Sun Mar 08, 2009 12:31 pm
by orbitcowboy
Giles wrote:
orbitcowboy wrote:Here is my way to compute this, its a bit more efficient :-):
It will really depend on the optimizer. For each array item you get a (almost) recursive call (which is not efficient at all) unless the optimizer is able to inline such a complex template construction. But it may even not compile with some old compilers so I am not sure of the success of the inline in any cases.
You are partially right. I know some older compilers do not support templates. But if look at the code, and you know a bit about templates, you see that the recursion is executed at compiletime, not at runntime! Its obvious, that this function is more efficient.
You should reserve templates for the cases they bring a real gain. Wisely wxWidgets has avoided their use.
I think templates are great, but one has to know what he is doing, when using templates :-)

Posted: Sun Mar 08, 2009 1:19 pm
by Giles
orbitcowboy wrote:You are partially right. I know some older compilers do not support templates. But if look at the code, and you know a bit about templates, you see that the recursion is executed at compiletime, not at runntime! Its obvious, that this function is more efficient.
Among the compilers that supported templates I think a lot did not manage the overloading of a template by a specific alternate definition for a given value of the generic type.

The template instances are built at compile time but without strong optimisation you will get a sort-of recursion at execution time. Without the optimisation the compiler will generate:

Code: Select all

template <> void vByteToBits<8>(int &number, unsigned short *bits)
{
    bits[7] = number & 1;
    number >>= 1;
    vByteToBits<7>(number,bits);
}
template <> void vByteToBits<7>(int &number, unsigned short *bits)
{
    bits[6] = number & 1;
    number >>= 1;
    vByteToBits<6>(number,bits);
}
template <> void vByteToBits<6>(int &number, unsigned short *bits)
{
    bits[5] = number & 1;
    number >>= 1;
    vByteToBits<5>(number,bits);
}
template <> void vByteToBits<5>(int &number, unsigned short *bits)
{
    bits[4] = number & 1;
    number >>= 1;
    vByteToBits<4>(number,bits);
}
template <> void vByteToBits<4>(int &number, unsigned short *bits)
{
    bits[3] = number & 1;
    number >>= 1;
    vByteToBits<3>(number,bits);
}
template <> void vByteToBits<3>(int &number, unsigned short *bits)
{
    bits[2] = number & 1;
    number >>= 1;
    vByteToBits<2>(number,bits);
}
template <> void vByteToBits<2>(int &number, unsigned short *bits)
{
    bits[1] = number & 1;
    number >>= 1;
    vByteToBits<1>(number,bits);
}
template <> void vByteToBits<1>(int &number, unsigned short *bits)
{
    bits[0] = number & 1;
    number >>= 1;
    vByteToBits<0>(number,bits);
}
template <> void vByteToBits<0>(int &, unsigned short *){}
This gives a lot of code and long execution time.
I can tell you after having worked on a project having replaced a lot of variability at execution time (polymorphism) by a variability at compile time (genericity) that this principle has been dumped for the next projects. This is too complex to manage (design, make, debug, maintain) and the little performance improvement is lost in executable size that has a negative impact on program start time and page faults at execution.

Templates may be a good solution if you want to write code that nobody can understand/maintain/modify but you.

Posted: Mon Mar 09, 2009 4:48 am
by matthew180
Your input and output are known fixed sizes, so drop the dynamic memory allocation, it is a waste of time and you have to remember to free the allocation. Since the calling function is going to be using the array of bits, leave the allocation up to the caller.

If you care about performance, unroll the loop. Personally I like things fast, so below is what I would do. A note about your original code, one of the slowest operations a CPU does division (not counting dividing by two using a shift.) So your divide followed by the modulus (the remainder of a division) are making that function about as slow as it could possibly be.

Also, without knowing what you are doing with the array of bit values, such a function seems like a waste of effort. Just test the bit you need directly.

Anyway, just another example of how you can do it (note the _alt function was slower on my system (AMD64))

Matthew

Code: Select all

#include <stdio.h>

void byte2bits(int num, int *bits);
void byte2bits_alt(int num, int *bits);

int
main(void)
{
    int num;
    int bits[8];

    num = 235;
    byte2bits(num, bits);
    printf("| 128 |  64 |  32 |  16 |  8  |  4  |  2  |  1  |\n");
    printf("|  %d  |  %d  |  %d  |  %d  |  %d  |  %d  |  %d  |  %d  |\n",
        bits[0], bits[1], bits[2], bits[3], bits[4], bits[5], bits[6], bits[7]);
    return 0;
}
// main()


/**
 * Convert an unsigned byte into an array of bit values
 *
 * @note Only the least significat byte of 'num' is considered.
 * @note 'bits' is assumed to be an array of integers with at least 8 elements.
 * @note Subscript 0 in the 'bits' array will contain the most significant bit.
 *
 * @parm[in]  num   Byte to convert to bit array
 * @parm[in]  bits  Array of integers to store bit values
 */
void
byte2bits(int num, int *bits)
{
    bits[0] = (num & 0x80) == 0 ? 0 : 1;
    bits[1] = (num & 0x40) == 0 ? 0 : 1;
    bits[2] = (num & 0x20) == 0 ? 0 : 1;
    bits[3] = (num & 0x10) == 0 ? 0 : 1;
    bits[4] = (num & 0x08) == 0 ? 0 : 1;
    bits[5] = (num & 0x04) == 0 ? 0 : 1;
    bits[6] = (num & 0x02) == 0 ? 0 : 1;
    bits[7] = (num & 0x01) == 0 ? 0 : 1;

    return;
}
// byte2bits()


void
byte2bits_alt(int num, int *bits)
{
    bits[7] = (num & 0x01); num >>= 1;
    bits[6] = (num & 0x01); num >>= 1;
    bits[5] = (num & 0x01); num >>= 1;
    bits[4] = (num & 0x01); num >>= 1;
    bits[3] = (num & 0x01); num >>= 1;
    bits[2] = (num & 0x01); num >>= 1;
    bits[1] = (num & 0x01); num >>= 1;
    bits[0] = (num & 0x01); num >>= 1;

    return;
}
// byte2bits_alt()