Ad:

C++ Discussion Thread
Unsolved
Views: 78312

You are currently viewing page 2 of this multi-page discussion thread; Jump to the first page

Mar 3rd, 2006

how to convert int to binary?

the best way to do this is to use the bits. The code would be:

C++ Syntax (Toggle Plain Text)
inline string to_binary( const int &x ) {
  int t;
  string ret;
  if( x > 0 ) t = x; else t = -1 * x;
  for( int i = 0; i < 32; ++i ) 
    if( t & ( 1 << i ) ) ret.push_back( '1' ); else ret.push_back( '0' );
  reverse( ret.begin(), ret.end() );
  ret.erase( 0, ret.find( '1' ) );
  if( ret.size() == 0 ) return "0";
  if( x < 0 ) return '-' + ret;
  return ret;
}
inline string to_binary( const int &x ) {
  int t;
  string ret;
  if( x > 0 ) t = x; else t = -1 * x;
  for( int i = 0; i < 32; ++i ) 
    if( t & ( 1 << i ) ) ret.push_back( '1' ); else ret.push_back( '0' );
  reverse( ret.begin(), ret.end() );
  ret.erase( 0, ret.find( '1' ) );
  if( ret.size() == 0 ) return "0";
  if( x < 0 ) return '-' + ret;
  return ret;
}

brahle

Reputation Points: 11

Solved Threads: 0

Newbie Poster

Offline

18 posts
since Mar 2006

Permalink

Mar 11th, 2006

Re: C++ Performance Tips

(Toggle Plain Text)

for( int i = 0; i < 32; ++i )

That's not very portable. Use something in <climits> or the C++ equivalent.

dwks

Reputation Points: 185

Solved Threads: 28

Posting Whiz in Training

Offline

269 posts
since Nov 2005

Permalink

Aug 8th, 2006

Re: C++ Performance Tips

Quote originally posted by bitforce ...

An easy way to swap 2 variables without using another variable:
C++ Syntax (Toggle Plain Text)
a=a+b;
b=a-b;
a=a-b;
a=a+b; b=a-b; a=a-b;

Easy way? I don't know, but sure it is inefficient (except if the optimizer is really good).

There *are* temporary variables if from an ISO standard point-of-view.

And, this algorithm can only be useful if (assuming an optimizer as good as Turbo C++ 1.0 optimizer or better, knowing that it is a very old compiler, with an obsolete optimizer):

Both a and b are in a register (otherwise, I don't know any architecture where the temporary would be avoided)
AND There is no builtin XCHG instruction at the assembly level (false for x86 and PowerPC)
AND The CPU lacks register (in that case, it is very probable that the CPU has a XCHG instruction).

And, in that case, you may, ocasionally (rarely) gain little performance... In all other cases, you just can pray that the optimizer will understand your bad code, and implement it in a correct way.
Most compilers I know produce bad code for that.

If you use a 25 years old compiler, with a very very bad optimizer, it might also be possible that this compiler lacks register variables...

In that case, the following code:

C++ Syntax (Toggle Plain Text)

a-=b;
b-=a;
a-=b;

Will produce something like (on x86-16, yep I can't imagine any such bad optimizer on x86-32):

C++ Syntax (Toggle Plain Text)
mov ax, [bp-8] ; timings on a k6-2 CPU (1)
sub ax, [bp-4]  ; 3
mov [bp-8],ax  ; 4 CPU cycles
 
mov ax,[bp-4]
sub ax,[bp-8]
mob [bp-4],ax
 
mov ax, [bp-8]
sub ax, [bp-4]
mov [bp-8],ax ;11.5 CPU cycle (i.e. the last one might be paired with the next instruction)
mov ax, [bp-8] ; timings on a k6-2 CPU (1)
sub ax, [bp-4]  ; 3
mov [bp-8],ax  ; 4 CPU cycles

mov ax,[bp-4]
sub ax,[bp-8]
mob [bp-4],ax

mov ax, [bp-8]
sub ax, [bp-4]
mov [bp-8],ax ;11.5 CPU cycle (i.e. the last one might be paired with the next instruction)

Note : If the optimizer is even more bad than what I described, the generated code might even be worst.
And, your code (which has temporaries), on the same compiler might be twice as slow...

The classical

C++ Syntax (Toggle Plain Text)

int c;
c=b;
b=a;
a=c;

Will produce something like:

C++ Syntax (Toggle Plain Text)
mov ax,[bp-4]
mov [bp-12],ax
 
mov ax,[bp-8]
mov [bp-4],ax
 
mov ax,[bp-12]
mov [bp-8],ax   ; 5.5 CPU cycles (on a K6-2 CPU)
mov ax,[bp-4]
mov [bp-12],ax

mov ax,[bp-8]
mov [bp-4],ax

mov ax,[bp-12]
mov [bp-8],ax   ; 5.5 CPU cycles (on a K6-2 CPU)

Note : I don't think that the compiler can generate worst code, even if there is no optimizer.

So, my point is that your code is *always* a bad idea.
This algorithm might only be used in some very special contexts, only on weird architectures (I don't know any such architecture, but it probably exists or existed), and at assembly level only!

Please, read my posts (SuperKoko) on these two threads (of another forum):
http://www.codeguru.com/forum/showthread.php?t=386883
http://www.codeguru.com/forum/showthread.php?t=383191

Also, remember that std::swap can be assumed as being optimal on your architecture : The compiler is allowed to do specific optimizations on it.

SuperKoko

Reputation Points: 35

Solved Threads: 0

Newbie Poster

Offline

10 posts
since May 2006

Permalink

Aug 9th, 2006

Re: C++ Performance Tips

Quote originally posted by BountyX ...

When you want to pass a constant variable, pass it by reference to save memory.

Example:
int example (const int value); // Uses more memory than
int example (const int &value); // this one

That's the opposite!

Using const references is a good idea for large objects (say, 16 bytes and more).
For very small objects (smaller than a pointer), if you're lucky, you'll not loose performance.
But it is quite probable that the compiler will generate more code, slower code, and use more stack memory (if the argument is not a lvalue).
And, moreover, it is very hard for the compiler to optimize the const-reference thing when the function is used across translation units boundaries (at least, for most compilers), because it must respect a calling convention, and can't know whether the function, internally, gets the address of the const reference.
In that case, the compiler can't replace such const-reference by a simple value.

Please read my posts on these two threads:
http://www.codeguru.com/forum/showthread.php?t=339608
http://www.codeguru.com/forum/showth...=392134&page=2

SuperKoko

Reputation Points: 35

Solved Threads: 0

Newbie Poster

Offline

10 posts
since May 2006

Permalink

Dec 15th, 2006

A General Performance Tip - Arithmetic involving powers of 2

Multiplication, division and modulus operations on powers of 2 can be made much faster using bitwise operators.

1. Modulo
Finding the modulus is particularly expensive. This operation can be performed mush faster using the & operator, because
a % n == a & (n-1) where n is power of 2.

2. Division
Division by a power of 2 can done faster using the >> operator.
a / n == a >> m, where n = 2^m

3. Multiplication
This is similar to division, except, use left shift << operator
a * n == a <<m , n = 2^m

vicky_dev

Reputation Points: 28

Solved Threads: 2

Junior Poster in Training

Offline

86 posts
since May 2005

Permalink

Dec 15th, 2006

Re: A General Performance Tip - Arithmetic involving powers of 2

Click to Expand / Collapse Quote originally posted by vicky_dev ...

Multiplication, division and modulus operations on powers of 2 can be made much faster using bitwise operators.

1. Modulo
Finding the modulus is particularly expensive. This operation can be performed mush faster using the & operator, because
a % n == a & (n-1) where n is power of 2.

2. Division
Division by a power of 2 can done faster using the >> operator.
a / n == a >> m, where n = 2^m

3. Multiplication
This is similar to division, except, use left shift << operator
a * n == a <<m , n = 2^m

Valid, albeit ancient, advice -- much like the XOR swap.

It's one of those things that language implementers knew about ages ago, and should be done by the compiler automagically (or it may take some optimization option).

Bottom line: don't do this unless your compiler sucks. Write code to multiply by 4 like this num*=4. Obfuscating it as num<<=2 will make your code look strangeto newbies, and it will look like a newbish hack to old timers (both making what you write a little suspect).

And don't forget that right-shifting signed values is implementation defined!

Last edited by Dave Sinkula; Dec 15th, 2006 at 9:54 pm.

Dave Sinkula

Team Colleague

Reputation Points: 2780

Solved Threads: 312

long time no c

Offline

4,790 posts
since Apr 2004

Permalink

Feb 21st, 2007

Re: C++ Performance Tips

A few more I find useful...

1. Replace switch-case/if-else with array-indexing:

c++ Syntax (Toggle Plain Text)
switch ( queue ) {
case 0 :   letter = 'W';
   break;
case 1 :   letter = 'S';
   break;
case 2 :   letter = 'U';
   break;
}
//or maybe
if ( queue == 0 )
  letter = 'W';
else if ( queue == 1 )
  letter = 'S';
else
  letter = 'U';
//A quicker method is to simply use the value as an
//index into a character array, eg.
static char *classes="WSU";
letter = classes[queue];
switch ( queue ) {
case 0 :   letter = 'W';
   break;
case 1 :   letter = 'S';
   break;
case 2 :   letter = 'U';
   break;
}
//or maybe
if ( queue == 0 )
  letter = 'W';
else if ( queue == 1 )
  letter = 'S';
else
  letter = 'U';
//A quicker method is to simply use the value as an
//index into a character array, eg.
static char *classes="WSU";
letter = classes[queue];

thekashyap

Reputation Points: 254

Solved Threads: 74

Practically a Posting Shark

Offline

804 posts
since Feb 2007

Permalink

Feb 21st, 2007

Re: C++ Performance Tips

2. I'm sure most ppl know this but writing as it's not already mentioned in this topic so far. Use unsigned int stored in registers for loop variables.
Reasons
1. unsigned int arithmatic is faster than signed int.
2. registers are registers ! They're simply faster than memory access.

c++ Syntax (Toggle Plain Text)
for( register unsigned int loop_variable = 0; loop_variable <=100000; i++ )
{ /*do your stuff*/ }
for( register unsigned int loop_variable = 0; loop_variable <=100000; i++ )
{ /*do your stuff*/ }

thekashyap

Reputation Points: 254

Solved Threads: 74

Practically a Posting Shark

Offline

804 posts
since Feb 2007

Permalink

Feb 21st, 2007

Re: C++ Performance Tips

3. Optimizing the breaking conditions in for loops. If you know that the loop variable's range is from 0 to some +ve number AND it doesn't matter which way you traverse while looping, you can optimize the loop like this:

c++ Syntax (Toggle Plain Text)
//original loop
for( int i = 0; i <= 30; i++ )
{/*do your stuff*/}
//optimized loop
for( int i = 30; i--; )
{/*do your stuff*/}
//original loop
for( int i = 0; i <= 30; i++ )
{/*do your stuff*/}
//optimized loop
for( int i = 30; i--; )
{/*do your stuff*/}

thekashyap

Reputation Points: 254

Solved Threads: 74

Practically a Posting Shark

Offline

804 posts
since Feb 2007

Permalink

Feb 21st, 2007

Re: C++ Performance Tips

4, Optimizing very small loops using switch-case.
When you know that the range of loop variable's value is
pretty small avoid the loop altogether.

c++ Syntax (Toggle Plain Text)
//unoptimized code
for( int i = some_small_positive_int; i--; )
{/*do your stuff with i*/}
 
//optimized based on the assumption that some_small_positive_int can only be from 1 to 7.
switch( i ) 
{ 
    case 7 : /*do your stuff with i*/ i++; 
    case 6 : /*do your stuff with i*/ i++; 
    case 5 : /*do your stuff with i*/ i++; 
    case 4 : /*do your stuff with i*/ i++; 
    case 3 : /*do your stuff with i*/ i++; 
    case 2 : /*do your stuff with i*/ i++; 
    case 1 : /*do your stuff with i*/ 
}
//unoptimized code
for( int i = some_small_positive_int; i--; )
{/*do your stuff with i*/}

//optimized based on the assumption that some_small_positive_int can only be from 1 to 7.
switch( i ) 
{ 
    case 7 : /*do your stuff with i*/ i++; 
    case 6 : /*do your stuff with i*/ i++; 
    case 5 : /*do your stuff with i*/ i++; 
    case 4 : /*do your stuff with i*/ i++; 
    case 3 : /*do your stuff with i*/ i++; 
    case 2 : /*do your stuff with i*/ i++; 
    case 1 : /*do your stuff with i*/ 
}

thekashyap

Reputation Points: 254

Solved Threads: 74

Practically a Posting Shark

Offline

804 posts
since Feb 2007

Previous
1
Page 2
3
4
5
Next

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Help with an overloaded operator

Next Thread in C++ Forum Timeline: Combined accessor/mutator?

DaniWeb Message

Cancel Changes

User Name
Password