checking first

[b][red]This message was edited by Gregry2 at 2006-9-30 11:46:52[/red][/b][hr]
These are example code clips, different code, but its supposed to do the same thing. The value 'bit' has to be the "index" of a bit in a byte, thus less that CHAR_BIT defined in limits.h. And the value 'byte', well, it follows suit.

[code]
byte=oldbit/CHAR_BIT;
bit=oldbit%CHAR_BIT;
[/code]

The below makes it more quicker when its oldbit already is in [0,CHAR_BIT]

[code]
if(oldbit>CHAR_BIT){
byte=oldbit/CHAR_BIT;
bit=oldbit%CHAR_BIT;
}
[/code]

Which is more efficient?

I'd prefer the first one. Although the second one makes saves the division (which is a costly operation compared to an extra jump) for one case, still, if either case is of no higher probability of the other, then it looks messy to make way for one case above the other. However, it would make more sense if the normal case is for oldbit to be lesser than CHAR_BIT...

{2}rIng

EDIT: changed code errors...

• : [b][red]This message was edited by Gregry2 at 2006-9-30 11:46:52[/red][/b][hr]
: These are example code clips, different code, but its supposed to do the same thing. The value 'bit' has to be the "index" of a bit in a byte, thus less that CHAR_BIT defined in limits.h. And the value 'byte', well, it follows suit.
:
: [code]
: byte=oldbit/CHAR_BIT;
: bit=oldbit%CHAR_BIT;
: [/code]
:
: The below makes it more quicker when its oldbit already is in [0,CHAR_BIT]
:
: [code]
: if(oldbit>CHAR_BIT){
: byte=oldbit/CHAR_BIT;
: bit=oldbit%CHAR_BIT;
: }
: [/code]
:
: Which is more efficient?
:
: I'd prefer the first one. Although the second one makes saves the division (which is a costly operation compared to an extra jump) for one case, still, if either case is of no higher probability of the other, then it looks messy to make way for one case above the other. However, it would make more sense if the normal case is for oldbit to be lesser than CHAR_BIT...
:
: Thanx for answering as always
: {2}rIng
:
: EDIT: changed code errors...
:

Are you sure you can't do this with binary operators?
It looks like that, but I don't know how the code will look like.

On machines of today, if I recall right, the division instruction takes as long as multiply and plus. The only difference is that it can't be paired, but that doesn't matter...

The jmp however takes a little more time. I don't think it's much.

As always: Happy programming!!!
• : Are you sure you can't do this with binary operators?
: It looks like that, but I don't know how the code will look like.
:
[green]
Yeah, you're right. Binary And with 0x07 to find the bit part, then right shift three times for the byte part...it would be great, but it would be supposedly be not as "portable" as dividing and finding the mod, since the latter uses CHAR_BIT, and there might be platforms "out-there" that might have some odd sized bytes that aren't eight bits long(although I haven't heard of any, are there any?)

I guess its better to do this, if I can be assured of no other platform with CHAR_BIT not being 0x08.
[/green]
:
: On machines of today, if I recall right, the division instruction takes as long as multiply and plus. The only difference is that it can't be paired, but that doesn't matter...
:
[green]
Paired? Do you mean operator precedence, or that it matters which operand is left or right?
[/green]
: The jmp however takes a little more time. I don't think it's much.
:
:
: As always: Happy programming!!!
:
[green]
Hehe. Thanx. People say programming is so complicated, but some people actually do it to relax...I dont know...
{2}rIng
[/green]
• : [b][red]This message was edited by Gregry2 at 2006-9-30 11:46:52[/red][/b][hr]
: These are example code clips, different code, but its supposed to do the same thing. The value 'bit' has to be the "index" of a bit in a byte, thus less that CHAR_BIT defined in limits.h. And the value 'byte', well, it follows suit.
:
: [code]
: byte=oldbit/CHAR_BIT;
: bit=oldbit%CHAR_BIT;
: [/code]
:
: The below makes it more quicker when its oldbit already is in [0,CHAR_BIT]
:
: [code]
: if(oldbit>CHAR_BIT){
: byte=oldbit/CHAR_BIT;
: bit=oldbit%CHAR_BIT;
: }
: [/code]
:
: Which is more efficient?
:
: I'd prefer the first one. Although the second one makes saves the division (which is a costly operation compared to an extra jump) for one case, still, if either case is of no higher probability of the other, then it looks messy to make way for one case above the other. However, it would make more sense if the normal case is for oldbit to be lesser than CHAR_BIT...
:
: Thanx for answering as always
: {2}rIng
:
: EDIT: changed code errors...
:
[green]
What are you trying to do with the code overall?
[/green]

• : : Are you sure you can't do this with binary operators?
: : It looks like that, but I don't know how the code will look like.
: :
: [green]
: Yeah, you're right. Binary And with 0x07 to find the bit part, then right shift three times for the byte part...it would be great, but it would be supposedly be not as "portable" as dividing and finding the mod, since the latter uses CHAR_BIT, and there might be platforms "out-there" that might have some odd sized bytes that aren't eight bits long(although I haven't heard of any, are there any?)
: [/green]

Then do like this:

[code]
bit = x & (CHAR_BIT - 1);
byte = x >> log(CHAR_BIT,2);
[/code]

OK, the last line was a little wierd, but it can still be accomplised by:
[code]
int log2bit 0;
int temp = CHAR_BIT;
while((temp>>1) > 0) ++log2bit;
[/code]

and then the code would be:
[code]
bit = x & (CHAR_BIT - 1);
byte = x >> log2bit;
[/code]

I think the first method will be faster, if you can make the compiler optimise log(CHAR_BIT,2) to 3. It's theoreticly possible.

: [green]
: I guess its better to do this, if I can be assured of no other platform with CHAR_BIT not being 0x08.
: [/green]

You can choose to program with wchars, wich are 16 bit wide I think.

: :
: : On machines of today, if I recall right, the division instruction takes as long as multiply and plus. The only difference is that it can't be paired, but that doesn't matter...
: :
: [green]
: Paired? Do you mean operator precedence, or that it matters which operand is left or right?
: [/green]

Never mind, but if you really got to know: Some instructions can be paired, ie executed at the same time, on newer proccessors.

: : The jmp however takes a little more time. I don't think it's much.
: :
: :
: : As always: Happy programming!!!
: :
: [green]
: Hehe. Thanx. People say programming is so complicated, but some people actually do it to relax...I dont know...
: {2}rIng
: [/green]
:

I would say it's stimulating, which is both...
• : Then do like this:
:
: [code]
: bit = x & (CHAR_BIT - 1);
: byte = x >> log(CHAR_BIT,2);
: [/code]
:
: OK, the last line was a little wierd, but it can still be accomplised by:
: [code]
: int log2bit 0;
: int temp = CHAR_BIT;
: while((temp>>1) > 0) ++log2bit;
: [/code]
:
: and then the code would be:
: [code]
: bit = x & (CHAR_BIT - 1);
: byte = x >> log2bit;
: [/code]
:

[green]
You're too smart . Yup, I think it'll work.

This is very unlikely, but the only problem will be if CHAR_BIT isn't a power of two...it most undoubtably will be though. I guess the only reason I'd even think it couldn't be is that I once read about a machine with a 7 bit long byte...but I read it on Fortran 77 paper that seemed to be from around that time...so, the platform is most likely beyond what one would say obsolete.
[/green]

: I think the first method will be faster, if you can make the compiler optimise log(CHAR_BIT,2) to 3. It's theoreticly possible.

[green]
I guess it is, since it can be calculated before runtime, but how likely is it? Since its mathematical, it might not be this, but it might be another case like strcpy() and movsb...lol.
[/green]

:
: I would say it's stimulating, which is both...
:

Some would say it conflicts, however, people listen to rock and hip-hop music and call it "relaxation", even though its energetic. I guess programming gives me something to think about, instead of thinking about something else.
{2}rIng
• : : [b][red]This message was edited by Gregry2 at 2006-9-30 11:46:52[/red][/b][hr]
: : These are example code clips, different code, but its supposed to do the same thing. The value 'bit' has to be the "index" of a bit in a byte, thus less that CHAR_BIT defined in limits.h. And the value 'byte', well, it follows suit.
: :
: : [code]
: : byte=oldbit/CHAR_BIT;
: : bit=oldbit%CHAR_BIT;
: : [/code]
: :
: : The below makes it more quicker when its oldbit already is in [0,CHAR_BIT]
: :
: : [code]
: : if(oldbit>CHAR_BIT){
: : byte=oldbit/CHAR_BIT;
: : bit=oldbit%CHAR_BIT;
: : }
: : [/code]
: :
: : Which is more efficient?
: :
: : I'd prefer the first one. Although the second one makes saves the division (which is a costly operation compared to an extra jump) for one case, still, if either case is of no higher probability of the other, then it looks messy to make way for one case above the other. However, it would make more sense if the normal case is for oldbit to be lesser than CHAR_BIT...
: :
: : Thanx for answering as always
: : {2}rIng
: :
: : EDIT: changed code errors...
: :
: [green]
: What are you trying to do with the code overall?
: [/green]
:

This is only an example. It doesn't have some deep shade of menaing beyond what what said in the first paragraph.
{2}rIng

• : : Then do like this:
: :
: : [code]
: : bit = x & (CHAR_BIT - 1);
: : byte = x >> log(CHAR_BIT,2);
: : [/code]
: :
: : OK, the last line was a little wierd, but it can still be accomplised by:
: : [code]
: : int log2bit 0;
: : int temp = CHAR_BIT;
: : while((temp>>1) > 0) ++log2bit;
: : [/code]
: :
: : and then the code would be:
: : [code]
: : bit = x & (CHAR_BIT - 1);
: : byte = x >> log2bit;
: : [/code]
: :
:
: [green]
: You're too smart . Yup, I think it'll work.
:
: This is very unlikely, but the only problem will be if CHAR_BIT isn't a power of two...it most undoubtably will be though. I guess the only reason I'd even think it couldn't be is that I once read about a machine with a 7 bit long byte...but I read it on Fortran 77 paper that seemed to be from around that time...so, the platform is most likely beyond what one would say obsolete.
: [/green]
:

No, this is wrong....
[code]
bit = x & (CHAR_BIT - 1);
byte = x >> log2bit;
[/code]
Is the same as

[code]
bit = x & 07;
byte = x >> 3;
[/code]
Which is wrong if you're trying to separate bytes...

This is how it should be done:
[code]
bit = x & ((1 << CHAR_BIT)-1);
byte = x >> CHAR_BIT;
[/code]
Which is the same as:
[code]
bit = x & 0xff;
byte = x >> 8;
[/code]

But I don't know what you're trying to do...

: : I think the first method will be faster, if you can make the compiler optimise log(CHAR_BIT,2) to 3. It's theoreticly possible.
:
: [green]
: I guess it is, since it can be calculated before runtime, but how likely is it? Since its mathematical, it might not be this, but it might be another case like strcpy() and movsb...lol.
: [/green]
:

• : [b][red]This message was edited by Gregry2 at 2006-9-30 11:46:52[/red][/b][hr]
: These are example code clips, different code, but its supposed to do the same thing. The value 'bit' has to be the "index" of a bit in a byte, thus less that CHAR_BIT defined in limits.h. And the value 'byte', well, it follows suit.
:
: [code]
: byte=oldbit/CHAR_BIT;
: bit=oldbit%CHAR_BIT;
: [/code]
:
: The below makes it more quicker when its oldbit already is in [0,CHAR_BIT]
:
: [code]
: if(oldbit>CHAR_BIT){
: byte=oldbit/CHAR_BIT;
: bit=oldbit%CHAR_BIT;
: }
: [/code]
:
: Which is more efficient?
:
: I'd prefer the first one. Although the second one makes saves the division (which is a costly operation compared to an extra jump) for one case, still, if either case is of no higher probability of the other, then it looks messy to make way for one case above the other. However, it would make more sense if the normal case is for oldbit to be lesser than CHAR_BIT...
:
: Thanx for answering as always
: {2}rIng
:
: EDIT: changed code errors...
:

Unless this is part of a time-critical part of the code, use the first version. No need to mess it up with bitwise operators either. And the size of a byte is 8 bits on all platforms, don't worry about that. If it for some insane reason would have a different number of bits, then it would likely be 16 and your code would still work (wchar_t in C99 is a diffent type, if you declare variables as char you will get 8 bits).
• : : [b][red]This message was edited by Gregry2 at 2006-9-30 11:46:52[/red][/b][hr]
: : These are example code clips, different code, but its supposed to do the same thing. The value 'bit' has to be the "index" of a bit in a byte, thus less that CHAR_BIT defined in limits.h. And the value 'byte', well, it follows suit.
: :
: : [code]
: : byte=oldbit/CHAR_BIT;
: : bit=oldbit%CHAR_BIT;
: : [/code]
: :
: : The below makes it more quicker when its oldbit already is in [0,CHAR_BIT]
: :
: : [code]
: : if(oldbit>CHAR_BIT){
: : byte=oldbit/CHAR_BIT;
: : bit=oldbit%CHAR_BIT;
: : }
: : [/code]
: :
: : Which is more efficient?
: :
: : I'd prefer the first one. Although the second one makes saves the division (which is a costly operation compared to an extra jump) for one case, still, if either case is of no higher probability of the other, then it looks messy to make way for one case above the other. However, it would make more sense if the normal case is for oldbit to be lesser than CHAR_BIT...
: :
: : Thanx for answering as always
: : {2}rIng
: :
: : EDIT: changed code errors...
: :
:
:
: Unless this is part of a time-critical part of the code, use the first version. No need to mess it up with bitwise operators either. And the size of a byte is 8 bits on all platforms, don't worry about that. If it for some insane reason would have a different number of bits, then it would likely be 16 and your code would still work (wchar_t in C99 is a diffent type, if you declare variables as char you will get 8 bits).

Just some remarks on the discussion.
- Don't worry about using /, >>, % or & for arithmetic. Most compilers are smart enough to generate bit-operations if the operand(s) are powers of 2. CHAR_BIT is a constant, so the compiler is able to optimize.

- Division is still slower than addition or subtraction, although not as much as on the 80486-and-before days.

- Pairing is something at the processor level for processors with multiple instruction-pipelines. Smart compilers know about it and use it.

- Conditional jmp's are extremely fast IF the result of the condition is the same most of the time. The processor uses 'a branch prediction' algorithm which causes the jmp to take no clocks in that case. However, if the result of the condition is different, the jmp is very slow.

Greets,
Eric Goldstein
http://www.gvh-maatwerk.nl

• :
: Just some remarks on the discussion.
: - Don't worry about using /, >>, % or & for arithmetic. Most compilers are smart enough to generate bit-operations if the operand(s) are powers of 2. CHAR_BIT is a constant, so the compiler is able to optimize.
:
:
: - Conditional jmp's are extremely fast IF the result of the condition is the same most of the time. The processor uses 'a branch prediction' algorithm which causes the jmp to take no clocks in that case. However, if the result of the condition is different, the jmp is very slow.
:

Isn't it more like that a no jmp takes 0 and a jmp takes a lot, if you get it...

How does that algorithm work?
It can't keep track of the most usual case of a comparison, as there's a lot of them.
• : :
: : Just some remarks on the discussion.
: : - Don't worry about using /, >>, % or & for arithmetic. Most compilers are smart enough to generate bit-operations if the operand(s) are powers of 2. CHAR_BIT is a constant, so the compiler is able to optimize.
: :
: :
: : - Conditional jmp's are extremely fast IF the result of the condition is the same most of the time. The processor uses 'a branch prediction' algorithm which causes the jmp to take no clocks in that case. However, if the result of the condition is different, the jmp is very slow.
: :
:
: Isn't it more like that a no jmp takes 0 and a jmp takes a lot, if you get it...
:
: How does that algorithm work?
: It can't keep track of the most usual case of a comparison, as there's a lot of them.
:

First, to Niklas
Here it is plainly. I have a size_t value which represents a certain number of bits. I need to know how many bytes this number is, and which bit of the most significant byte it would be. Thus, the most ready solution would be the one I offered.

So, I'm not seperating bytes, or rather, I think you meant nybbles?...

To others...
Its like an operator, so its used commonly. It wouldn't hurt to use binary ops, would it?
{2}rIng