faqcat38c2.html

this is a mirrored site c-faq. thought might need offline

<p>References:

PCS Sec. 11 p. 179
<hr><hr><hr>
<a name="hexio">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../misc/hexio.html"><!-- qtag -->Question 20.10</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
How can I convert integers to
binary or
hexadecimal?

</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
Make sure you really know what you're asking.
Integers are stored internally in binary,
although for most purposes it is not incorrect
to think of them as being in
octal, decimal, or hexadecimal,
whichever is convenient.
The base in which a number is expressed matters only when that
number is read in from or written out to the outside world,
either in the form of
a source code constant
or in the form of I/O
performed by a program.
</p><p>In source code,
a non-decimal base is indicated
by
a leading <TT>0</TT> or <TT>0x</TT>
(for octal or hexadecimal, respectively).
During I/O, the base of a formatted number is controlled
in the
<TT>printf</TT>
and <TT>scanf</TT>
family
of functions
by the choice of format specifier
(<TT>%d</TT>, <TT>%o</TT>, <TT>%x</TT>, etc.)
and in the <TT>strtol</TT>
and <TT>strtoul</TT>
functions
by the third argument.
During
<em>binary</em> I/O,
however, the base again becomes immaterial:

if numbers are being read or written as individual bytes
(typically with <TT>getc</TT> or <TT>putc</TT>),
or as multi-byte words
(typically with <TT>fread</TT> or <TT>fwrite</TT>),
it is meaningless to ask what ``base'' they are in.
</p><p>If what you need is formatted binary conversion,
it's easy enough to do.
Here is a little function
for formatting
a number in a requested base:


<pre>
char *
baseconv(unsigned int num, int base)
{
	static char retbuf[33];
	char *p;

	if(base &lt; 2 || base &gt; 16)
		return NULL;

	p = &amp;retbuf[sizeof(retbuf)-1];
	*p = '\0';

	do {
		*--p = "0123456789abcdef"[num % base];
		num /= base;
	} while(num != 0);

	return p;
}
</pre>

(Note that this function, as written,
returns a pointer to static data,
such that only one of its return values can be used at a time;
see question <a href="faqcatbafd.html?sec=malloc#retaggr">7.5a</a>.
A better size for the <TT>retbuf</TT> array
would be <TT>sizeof(int)*CHAR_BIT+1</TT>;
see question <a href="faqcat1d60.html?sec=stdio#sprintfsize">12.21</a>.)
</p><p>For more information about ``binary'' I/O,
see
questions <a href="faqcat6b6b.html?sec=struct#io">2.11</a>, <a href="faqcat1d60.html?sec=stdio#binaryio">12.37</a>, and <a href="faqcat1d60.html?sec=stdio#extconform">12.42</a>.
See also questions
<a href="faqcate107.html?sec=charstring#asciivals">8.6</a>
and
<a href="faqcat1067.html?sec=lib#itoa">13.1</a>.
</p><p>Additional links:
A
<a href="faqcat38c2.html?sec=misc#btod">long reply</a>
I sent to someone who was asking how to write a
``binary to decimal'' conversion function
</p>

<p>References:

ISO Secs. 7.10.1.5,7.10.1.6
<hr><hr><hr>
<a name="base2">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../misc/base2.html"><!-- qtag -->Question 20.11</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
Can I use base-2 constants
(something like <TT>0b101010</TT>)?
<br>Is there a
<TT>printf</TT> format for binary?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
No, on both counts,
although there are various preprocessor tricks you can try
(see the links below).
You can convert base-2 string representations
to integers with <TT>strtol</TT>.
If you need to print numbers out in base 2,
see
the example code in
question <a href="faqcat38c2.html?sec=misc#hexio">20.10</a>.
</p><p>Additional links:
<br>
<br>
<a href="http://home.att.net/~jackklein/ctips01.html#binary_in">example by Jack Klein</a>
<br>
<br>



<a href="../../misc/sd27.html" rel=subdocument>preprocessor trick</a>
by Karl Heuer
<br>
<br>
<a href="../../misc/sd28.html" rel=subdocument>prettier preprocessor trick</a>
by Bill Finke
<hr><hr><hr>
<a name="bitcount">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../misc/bitcount.html"><!-- qtag -->Question 20.12</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
What is the most efficient way to count the number of bits
which are set in
an integer?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
Many ``bit-fiddling'' problems
like this one
can be
sped up and streamlined using
lookup tables
(but see
question <a href="faqcat38c2.html?sec=misc#efficiency">20.13</a>).
Here is a little function which computes the number of bits in a value,
4 bits at a time:
<pre>
static int bitcounts[] =
	{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};

int bitcount(unsigned int u)
{
	int n = 0;

	for(; u != 0; u &gt;&gt;= 4)
		n += bitcounts[u &amp; 0x0f];

	return n;
}
</pre>
<hr><hr><hr>
<a name="efficiency">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../misc/efficiency.html"><!-- qtag -->Question 20.13</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
What's the best way of making my program efficient?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
By picking good algorithms,
implementing them carefully,
and making sure that your program isn't doing any extra work.
For example,
the most microoptimized character-copying loop in the world
will be beat by code which avoids having to copy characters at all.
</p><p>When worrying about efficiency,
it's important to keep several things in perspective.
First of all,
although efficiency is
an enormously popular
topic,
it
is not
always as important
as people tend to think it is.
Most of the code in most programs is not time-critical.
When code is not time-critical,
it is
usually
more important that it be written clearly and portably
than that it be written maximally efficiently.
(Remember that
computers are very, very fast,
and that seemingly ``inefficient'' code
may be quite efficiently compilable,
and
run without apparent delay.)
</p><p>It is notoriously difficult to predict
what
the ``hot spots'' in a program will be.
When efficiency is a concern,
it is important to use profiling software
to determine which parts of the program deserve attention.
Often, actual computation time is swamped by peripheral tasks
such as I/O and memory allocation,
which can be sped up by using buffering and caching
techniques.
</p><p>Even
for
code that <em>is</em> time-critical,
one of the least effective optimization techniques
is to fuss with
the coding details.
Many of the ``efficient coding tricks''
which are frequently suggested
are performed automatically
by even
simpleminded
compilers.
Heavyhanded optimization attempts can make code so
bulky that performance is actually degraded,
by increasing the number of page faults or
by
overflowing 
instruction caches or pipelines.
Furthermore,
optimization tricks
are rarely portable
(i.e. they may speed things up on one machine
but slow them down on another).
In any case,
tweaking the coding usually results in
at best linear performance improvements;
the big payoffs are in better
algorithms.
</p><p>If the performance of your code is so important
that you are willing to invest programming time
in source-level optimizations,
make sure that you are using
the best optimizing compiler
you can afford.
(Compilers,
even mediocre ones,
can perform optimizations
that are impossible at the source level).
</p><p>When efficiency is truly
important,
the best algorithm has been chosen,
and even the coding details matter,
the following suggestions may be useful.
(These are mentioned merely
to keep followups down;
appearance here does
<em>not</em>
necessarily
constitute endorsement by the author.
Note that several of these techniques
cut both ways,
and
may make things worse.)
<OL><li>Sprinkle the code liberally with <TT>register</TT> declarations for
oft-used variables;
place them in inner blocks,
if applicable.
(On the other hand, most modern compilers ignore <TT>register</TT>
declarations, on the assumption that they can perform register 
analysis and assignment better than the programmer can.)
<li>Check the algorithm carefully.
Exploit symmetries where possible to reduce the number of explicit cases.
<li>Examine the control flow:
make sure that common cases are checked for first,
and handled more easily.
If one side of
an expression involving <TT>&amp;&amp;</TT> or <TT>||</TT>
will usually determine the outcome,

make it the left-hand side,
if possible.
(See also question <a href="faqcatee08.html?sec=expr#shortcircuit">3.6</a>.)
<li>Use <TT>memcpy</TT> instead of
<TT>memmove</TT>,
if appropriate
(see question
<a href="faqcat7d4b.html?sec=ansi#memmove">11.25</a>).
<li>Use machine- and vendor-specific routines and <TT>#pragma</TT>s.
<li>Manually place
common subexpressions
in temporary variables.
(Good compilers do this for you.)
<li>Move critical, inner-loop code
out of functions
and into macros or in-line functions
(and out of the loop, if invariant).
If the termination condition of a loop is a complex
but loop-invariant
expression,
precompute it and place it in a temporary variable.
(Good compilers do these for you.)
<li>


Change recursion to iteration, if possible.
<li>Unroll small loops.

<li>Discover whether
<TT>while</TT>, <TT>for</TT>,
or <TT>do/while</TT>
loops produce the best code under your compiler,
and whether incrementing or decrementing
the loop control variable
works best.
<li>Remove <TT>goto</TT> statements--some compilers can't optimize 
as well in their presence.
<li>Use pointers rather than array subscripts to step through arrays
(but see question <a href="faqcat38c2.html?sec=misc#eff2">20.14</a>).
<li>Reduce precision.
(Using <TT>float</TT> instead of <TT>double</TT>
may result in faster,
single-precision arithmetic under an ANSI compiler,
though
older compilers convert everything to <TT>double</TT>,
so using <TT>float</TT> can also be slower.)
Replace time-consuming trigonometric and logarithmic functions
with your own,
tailored to the range and precision you need,
and perhaps using table lookup.
(Be sure to give your versions
<em>different</em>
names;
see question <a href="faqcatd3c2.html?sec=decl#namespace">1.29</a>.)
<li>Cache or precompute
tables of frequently-needed values.
(See also question <a href="faqcat38c2.html?sec=misc#bitcount">20.12</a>.)
<li>


Use standard library functions in preference to your own.
(Sometimes the compiler
inlines or
specially optimizes
its own functions.)
On the other hand,
if your program's calling patterns are
particularly regular,
your own special-purpose implementation may be able to beat
the library's general-purpose version.
(Again, if you do write your own version,
give it a different name.)
<li>As a last,
<em>last</em>
resort, hand-code critical routines in assembly language
(or hand-tune the compiler's assembly language output).
Use <TT>asm</TT> directives, if possible.
</OL></p><p>Here are some things <em>not</em> to worry about:
<OL><li>17x.
whether <TT>i++</TT> is faster than <TT>i&nbsp;=&nbsp;i&nbsp;+&nbsp;1</TT>
<li>18x.
whether <TT>i&nbsp;&lt;&lt;&nbsp;1</TT>
(or <TT>i&nbsp;&gt;&gt;&nbsp;1</TT>, or <TT>i&nbsp;&amp;&nbsp;1</TT>)
is faster than <TT>i&nbsp;*&nbsp;2</TT>
(respectively <TT>i&nbsp;/&nbsp;2</TT>, <TT>i&nbsp;%&nbsp;2</TT>).
</OL></p><p>(These are examples of optimizations which compilers regularly 
perform for you;
see questions <a href="faqcat38c2.html?sec=misc#eff2">20.14</a>
and <a href="faqcat38c2.html?sec=misc#shifts">20.15</a>.)
</p><p>It is not the intent here to suggest that efficiency can be
completely ignored.
Most of the time,
however,
by simply paying attention to good algorithm choices,
implementing them
cleanly,
and avoiding obviously inefficient blunders
(i.e. make sure you don't end up with an
O(n**3)
implementation of an
O(n**2)
algorithm),

perfectly acceptable results can be achieved.
</p><p>For more discussion of efficiency tradeoffs,
as well as good advice on how to improve efficiency when it is important,
see
chapter 7 of Kernighan and Plauger's
<I>The Elements of Programming Style</I>,
and Jon Bentley's
<I>Writing Efficient Programs</I>.
</p><p>See also question <a href="faqcataae2.html?sec=style#vsefficiency">17.11</a>.
<hr><hr><hr>
<a name="eff2">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../misc/eff2.html"><!-- qtag -->Question 20.14</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
Are pointers really faster than arrays?
How much do function calls slow things down?
Is <TT>++i</TT> faster than <TT>i&nbsp;=&nbsp;i&nbsp;+&nbsp;1</TT>?
</p><p><hr>
<p>
<font face=Helvetica size=8 color=blue><b>A:</b></font>
Precise answers to these and many similar questions
depend
of course
on the processor and compiler in use.
If you simply must know,
you'll have to time test programs carefully.
(Often the differences are so slight that
hundreds of
thousands of iterations are required even to see them.
<a href="../../misc/subtle.html" rel=subdocument>[footnote]</a>
Check the compiler's assembly language output,
if available,
to see if two
purported alternatives aren't compiled identically.)
</p><p>For conventional machines,
it is usually
faster to march through large arrays with
pointers rather than array subscripts,
but for some processors the reverse is true.
(Better compilers should
generate good code
regardless of which notation you use,
though





it's arguably easier for a compiler
to convert array indices to pointers than vice versa<a href="../../misc/fn98.html" rel=subdocument>[footnote]</a>
.)
</p><p>Function calls,
though obviously incrementally slower than in-line code,
contribute so much to modularity and code clarity
that there is rarely good reason to avoid them.
(Actually, by reducing bulk,
functions can improve performance.)
Also,



some compilers are able to expand
small, critical-path functions
in-line,
either as an optimization or at the programmer's request.
</p><p>Before rearranging expressions such as <TT>i&nbsp;=&nbsp;i&nbsp;+&nbsp;1</TT>,
remember that you are dealing with a compiler,
not a keystroke-programmable calculator.
Any decent compiler
will generate identical code for <TT>++i</TT>, <TT>i&nbsp;+=&nbsp;1</TT>,
and <TT>i&nbsp;=&nbsp;i&nbsp;+&nbsp;1</TT>.
The reasons for using <TT>++i</TT> or <TT>i&nbsp;+=&nbsp;1</TT> over <TT>i&nbsp;=&nbsp;i&nbsp;+&nbsp;1</TT>
have to do with style, not efficiency.
(See also question
<a href="faqcatee08.html?sec=expr#plusplus">3.12b</a>.)
<hr><hr><hr>
<a name="shifts">
<h1>
comp.lang.c FAQ list
<font color=blue>&middot;</font>
<a href="../../misc/shifts.html"><!-- qtag -->Question 20.15</a>
</h1>
<p>
<font face=Helvetica size=8 color=blue><b>Q:</b></font>
I've been replacing multiplications and divisions
with shift operators,