Has anyone have any ideas for a possibly more efficient approach to
conditionally executing code based on bits being set (to zero)?
example attempt: If the particular bit is set to 0, do something (in
this case increment a particular output)
void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..
}
}
11  1931 
On 2008-04-19 21:11, joe wrote:
Has anyone have any ideas for a possibly more efficient approach to
conditionally executing code based on bits being set (to zero)?
example attempt: If the particular bit is set to 0, do something (in
this case increment a particular output)
void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..
}
}
#include <iostream>
void foo(unsigned char input, int* output)
{
for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
if (input & (1 << i))
++output[i];
}
int main()
{
int out[sizeof(unsigned char) * 8];
for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
out[i] = 0;
foo(0xAA, out);
for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
std::cout << out[i] << "\n";
}
--
Erik Wikström
On 19 avr, 21:11, joe <joeyc...@mail. comwrote:
Has anyone have any ideas for a possibly more efficient
approach to conditionally executing code based on bits being
set (to zero)?
example attempt: If the particular bit is set to 0, do
something (in this case increment a particular output)
void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..
}
In this particular case:
void
foo( unsigned input, int* output )
{
while ( input != 0 ) {
if ( (input & 1) != 0 ) {
++ (*output) ;
}
++ output ;
input >>= 1 ;
}
}
(It's a bit tricker with a signed int, since the sign may be
propagated by the right shift. In general, I would avoid signed
types when dealing with bits.)
--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
On Apr 20, 4:42 am, James Kanze <james.ka...@gm ail.comwrote:
On 19 avr, 21:11, joe <joeyc...@mail. comwrote:
Has anyone have any ideas for a possibly more efficient
approach to conditionally executing code based on bits being
set (to zero)?
example attempt: If the particular bit is set to 0, do
something (in this case increment a particular output)
void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..
}
In this particular case:
void
foo( unsigned input, int* output )
{
while ( input != 0 ) {
if ( (input & 1) != 0 ) {
++ (*output) ;
}
++ output ;
input >>= 1 ;
}
}
(It's a bit tricker with a signed int, since the sign may be
propagated by the right shift. In general, I would avoid signed
types when dealing with bits.)
Thanks. Playing around with it more, I found that the statement:
if( ~input & 1) was faster than if( (input & 1) != 0) on my
particular compiler (gnu). Looking at the assembly output I can see
why; although some other compilers I've tried optimize both to the
same machine code. Don't know if that's a missed gnu optimization, or
gnu is just being more pedantic about violating some standards rule.
It also proved faster to create a templated compile-time loop instead
of an explicit loop with a loop conditional.
Thanks
On 20 avr, 15:38, joe <joeyc...@mail. comwrote:
On Apr 20, 4:42 am, James Kanze <james.ka...@gm ail.comwrote:
[...]
Thanks. Playing around with it more, I found that the statement:
if( ~input & 1) was faster than if( (input & 1) != 0) on my
particular compiler (gnu).
And platform. I wouldn't really worry about it; the difference
is unlikely to be measurable.
Looking at the assembly output I can see why; although some
other compilers I've tried optimize both to the same machine
code. Don't know if that's a missed gnu optimization, or gnu
is just being more pedantic about violating some standards
rule.
If the results are the same, then the optimization is legal.
It also proved faster to create a templated compile-time loop
instead of an explicit loop with a loop conditional.
How can you create a templated compile-time loop when the number
of times you go through the loop isn't known until runtime?
--
James Kanze (GABI Software) email:ja******* **@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
And platform. I wouldn't really worry about it; the difference
is unlikely to be measurable.
Looking at the assembly output I can see why; although some
other compilers I've tried optimize both to the same machine
code. Don't know if that's a missed gnu optimization, or gnu
is just being more pedantic about violating some standards
rule.
If the results are the same, then the optimization is legal.
It also proved faster to create a templated compile-time loop
instead of an explicit loop with a loop conditional.
How can you create a templated compile-time loop when the number
of times you go through the loop isn't known until runtime?
The difference was pretty measurable. About a 20% speed-up for the
total application. As for the loop, the number of iterations is
known at compile time (there are only so many bits in an unsigned int
to loop through). In this particular application, it is equally as
likely for any bit to be set, so there is no advantage to trying to
exit early.
Thanks for the comments
joe wrote:
...
Playing around with it more, I found that the statement:
if( ~input & 1) was faster than if( (input & 1) != 0) on my
particular compiler (gnu).
Except that it is not the same thing. More like the opposite of the original
statement.
Looking at the assembly output I can see
why; although some other compilers I've tried optimize both to the
same machine code. Don't know if that's a missed gnu optimization, or
gnu is just being more pedantic about violating some standards rule.
I find it rather unusual. Could you please post the assembly code you are
referring to?
--
Best regards,
Andrey Tarasevich
On Sat, 19 Apr 2008 21:11:06 GMT, Erik Wikström
<Er***********@ telia.comwrote in comp.lang.c++:
On 2008-04-19 21:11, joe wrote:
Has anyone have any ideas for a possibly more efficient approach to
conditionally executing code based on bits being set (to zero)?
example attempt: If the particular bit is set to 0, do something (in
this case increment a particular output)
void foo(int input,int* output)
{
if( !(input & 1) )
{
output[0] ++;
}
if( !(input & 2) )
{
output[1]++;
}
if( !(input & 4) )
{
output[2]++;
}
..etc..
}
}
#include <iostream>
void foo(unsigned char input, int* output)
{
for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
The line above could fail miserably on platforms where there are more
than 8 bits in an unsigned char, and yes they do exist. And have C++
compilers.
if (input & (1 << i))
++output[i];
}
int main()
{
int out[sizeof(unsigned char) * 8];
for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
The line above could fail miserably on platforms where there are more
than 8 bits in an unsigned char, and yes they do exist. And have C++
compilers.
out[i] = 0;
foo(0xAA, out);
for (int i = 0; i < sizeof(unsigned char) * 8; ++i)
The line above could fail miserably on platforms where there are more
than 8 bits in an unsigned char, and yes they do exist. And have C++
compilers.
std::cout << out[i] << "\n";
}
There's a perfectly good macro named CHAR_BIT in <climits>/<limits.h>,
that eliminates this completely needless unportability.
--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++ http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html
On Apr 20, 4:57 pm, Andrey Tarasevich <andreytarasev. ..@hotmail.com>
wrote:
joe wrote:
...
Playing around with it more, I found that the statement:
if( ~input & 1) was faster than if( (input & 1) != 0) on my
particular compiler (gnu).
Except that it is not the same thing. More like the opposite of the original
statement.
You are correct. The original code was !(input & 1), which is
equivalent to the altered (~input & 1).
I find it rather unusual. Could you please post the assembly code you are
referring to?
The following program:
#include <iostream>
int main(int arg, char **argv)
{
int input = atoi(argv[1]);
int a = 0;
if(~input & 1) a++;
if(~input & 2) a++;
if(~input & 4) a++;
if(~input & 8) a++;
if(~input & 16) a++;
std::cout<<a<<s td::endl;
}
using "g++ 3.4.6 -O3 -S" on linux generates code that seems to have 3
less machine instructions than if I replace the lines with if(!(input
& ...)) a++;
It runs slower, and other compilers produce equally sized machine
output and have no speed improvement.
Thanks,
Joe This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Tor Erik Sønvisen |
last post by:
Hi
I need a time and space efficient way of storing up to 6 million bits. Time
efficency is more important then space efficency as I'm going to do searches
through the bit-set.
regards tores
|
by: Thomas Paul Diffenbach |
last post by:
I'm trying to write a space efficient string (nul terminated array
of char), storing the characters directly unless the number of
characters is too large to be so stored, and storing a pointer to
other storage otherwise.
Rather than lose space to padding by just using a sentinal bool to
indicate which member of the union has been written to, I want to
overload the last character of the directly stored string as the
sentinal.
|
by: Vivek Mandava |
last post by:
Hello All,
Which one is an expensive operation?
'>' or '==" ?
I know this won't matter much. However, if I'm executing this
operation million times, I would prefer the better choice.
My gut feeling is that '>' should be efficient. However, when
translated to assembly code all it generates is "cmpl" instruction
|
by: hoopsho |
last post by:
Hi Everyone,
I am trying to write a program that does a few things very fast
and with efficient use of memory...
a) I need to parse a space-delimited file that is really large,
upwards fo a million lines.
b) I need to store the contents into a unique hash.
c) I need to then sort the data on a specific field.
d) I need to pull out certain fields and report them to the user.
|
by: nessuno |
last post by:
I can't find any discussion of this question in this NG.
I'd like to implement some variable precision integer arithmetic in C,
and do it efficiently. A problem arises with the divide/remainder
operations. I'm using gcc on x86, but a lot of what I say applies to
other architectures.
First, I assume the div and ldiv functions are more efficient than
using / and % (obviously it depends on the compiler and level of
optimization, but...
| | |
by: aurgathor |
last post by:
I use BC 5.02 (long is 32 bit) and I wonder if
there's any efficient code that would allow me
to left shift 64 bit values that I currently use
this way:
typedef struct {
unsigned long lsLong;
unsigned long msLong;
} b64_struct;
|
by: Alan Little |
last post by:
I have affiliates submitting batches of anywhere from 10 to several
hundred orders. Each order in the batch must include an order ID,
originated by the affiliate, which must be unique across all orders in
all batches ever submitted by that affiliate. I'm trying to figure out
the most efficient way to check the uniqueness of the order ID.
Order data is being submitted to Zen Cart, and also stored in custom
tables. I have created a unique...
|
by: spekyuman |
last post by:
Pointer and reference arguments provide C++ programmers with the
ability to modify objects. What is more efficient, passing arguments
via pointer or reference? Avoid the stereotypical urge of debating
effective coding style. Instead, think of particular scenarios:
passing a 512MB object to function. Think behind the scenes, from the
stack and heap to the physical linking and build of the program.
|
by: Lie Ryan |
last post by:
On Fri, 10 Oct 2008 00:30:18 +0200, Hendrik van Rooyen wrote:
You'll find that in most cases, using integer or Boolean is enough. There
are some edge cases, which requires bit addressing for speed or memory
optimizations, in python, the usual response to that kind of optimization
requirement is to move that part of the code to C.
If, for the more usual case, you require the bit addressing because the
data structure is more convenient...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| | |
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
| | |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
