|
|
Do you have a topic you'd like Thorkil to write about? Click
here to send a request. |
|
Bit Testing in Integer Values
By Thorkil B. Rassmussen
When handling numbers in higher programming
languages you often have the need to test the value of a single bit
or a set of bits inside an integer-type variable. A typical example
is when you need to test if a number is odd or even, but it may also
be to isolate a range of bits for further processing.
In Ada you have to use a combination of divide and
mod/rem operations. The mod and rem operators have properties that
distinguish them, and where the rem operator is the result of
executing a machine divide operation and then choosing the
remainder, the mod operator has further demands about the sign of
the result. So in general obtaining the remainder is the faster
choice, unless the mod operator characteristics are needed (the
programmer may know about the sign of the operands being both zero,
but the code generator may not know).
One important characteristic of the mod operator
when the second operand is a power of 2, e.g. 2 ** N, is that the
result is always the low N bits, and a code generator can just mask
out the N low bits with a simple AND operation. So to test if an
integer is odd, simply write:
... intg mod 2 = 1 ...
and the code should simply load the intg value and then issue an AND
instruction with the mask set to 1.
To get the low 8 bits use:
... intg mod 256 ... (or ... intg mod 16#100#
...)
where the mask used will then be 16#FF# (one less than the
power of two value).
This technique can be used to isolate almost all bit
sequences in an integer, except for the sequence beginning next to
the sign bit, as this would need a constant, e.g. 2**31, that is
outside the range of the (32-bit) integer type. Instead the possible
sign must be removed:
intg_nat : Natural; -- use a
non-negative temporary
if intg < 0 then
intg_nat := intg - integer’first; -- remove the
sign bit
else
intg_nat := intg;
end if;
Getting to a string of bits starting some bits
inside our integer value (e.g. from P to N) will require a division
in Ada83 (Ada95 may use intrinsics) with a power of 2, e.g., 2**P.
Here P=0 is the least significant start bit. Divisions however
suffer from the same problem as remainder that the code cannot
merely make a right shift, since this would be incorrect for signed
integer values. The trick here is to inform the code generator that
the value to divide with a power of 2 is positive, and that may be
done by making a mod operation that includes the top bit of the bit
string to get to. So here we can reuse the observations above, and
first isolate the needed bits, using a mod operation, and then shift
the result in place using a divide with a power of 2.
As an example, to isolate the top bit (bit 7) of the
eight least significant bits in an efficient manner, you can
write:
... (intg
mod 256) / 128 ...
Generally for bit P:
... (intg
mod (2**(P+1)) / (2**P)) ...
For bits P..N (P <= N) the divider shall be
(2**P), and the result delivers (N-P+1) bits.
... (intg
mod (2**N) / (2**P)) ...
For P = 0, the division can be avoided (and would
probably be optimized away anyway).
Again, if N is denoting the bit next to the sign bit
use the technique above and then use this approach:
-- to then get bits P..30 use:
bits_P_30 := intg_nat / (2**P); -- to get bits P..30 (sign bit
is 31)
-- to also include the sign bit the
original sign must be used:
if intg < 0 then - only add, when the sign bit
is on
bits_P_31 := intg_nat / (2**P) + 2**(31-P); - P <= 30
end if; -- this is however not very efficient
It is important that the mod and divide operands are
written as literal constants, and writing hexadecimal numbers makes
it clearer which bits are in play, as both operands must have only
one bit set each (one non-zero hex-digit only being 1, 2, 4 or 8).
Using binary numbers is another option though they may be long, but
grouping them may help: 2#1000_0000# (bit 7 set alone).
A clever code generator should generate code for the
general case like this:
MOV load intg value
AND with (mod-value-1) (all 1 bit sequence)
SHR with P shifts
The above technique can be used in most contexts
without the need of using representation specifications which
interpret an integer layout as a combination of record fields that
denote bits and/or small packed values. The representation
specifications suffer the need to be endian-specific which does not
affect the arithmetic conversions.
It will be advisable to check that the code generator makes the
optimal code called for by disassembling a sample. Making more
elaborate solutions, such as inline functions usually generates much
more and slower code than the straightforward use of mod and
division.
 |
About the Author
Thorkil Bjørn Rassmussen has worked with DDC-I for
over 20 years. He has a Master of Science, Computer Science, from
University of Copenhagen. Thorkil has substantial experience with
all of the DACS tools and is the key individual involved in all FAA
certifications for the DACS product line. Thorkil lives with his
wife Jane and two children Jonas and Tine, just outside of
Copenhagen, Denmark.
|
[
Back to Top ]
3rd Party Update
Ada Distilled
A Compact Introduction
to the Ada Programming Language
 Are
you an experienced programmer that wishes to learn the Ada
programming language at the programming level? Check out a book
called "Ada Distilled" written by Richard Riehle, an Ada
advocate dedicated to promoting Ada.
Ada Distilled is designed to be a compact
introduction to Ada for those with some knowledge of computer
programming. It is not intended to be a comprehensive treatment of
Ada; other books fill that role. Ada Distilled is designed around
the idea that each concept can be best appreciated when the
programmer is able to see an example fully coded in a small working
program. That is, the book avoids using program fragments as much as
possible. By starting with a working example, the newcomer to the
language can easily experiment with extensions to the example.
In addition, instead of separating the
explanation of a program from its source code, Richard annotates
each line of code with standard comments. These line-by-line
comments are useful to those who have used Ada Distilled.
The first version of Ada Distilled was in
black-and-white text, and has recently been updated to a color
document, as well as updated with improved examples. Although most
of the book is focused on elementary aspects of the language, it
became clear that two topics need more attention than others because
they seemed confusing to some newcomers. One of these was generic
formal package parameters, and the other is access types, especially
access to subprograms and access to declared objects. Even
experienced Ada programmers seem to have difficulty with these
topics. Including these examples has proven useful to those who
already know most of the other material in Ada Distilled.
Ada Distilled is available for download from the
AdaIC website at http://www.adaic.org/docs/distilled/adadistilled.pdf. The text of the book is PDF format. There is separate file with a
set of all the programs in source code format so the student can
compile and experiment with them.
About Richard Riehle:
Richard is the founder of AdaWorks Software Engineering (http://www.adaworks.com),
a company dedicated to promoting Ada, training those who want to
learn more about Ada, and assisting those who are building systems
with Ada. For the last three years, Richard has been at the Naval
Postgraduate School as a Visiting Professor. At NPS he teaches
classes in software engineering, programming languages, and fills in
as a teacher for general computer science classes such as operating
systems and data structures. He is also engaged in several research
efforts including a project related to software deception and
software architecture.
[
Back to Top ]
By Linda Rising
risingl@acm.org
www.lindarising.org
We know our organizations must be agile, and we
must change in order to survive, but we also know that’s easier
said than done. I thought I would tell you about a few good patterns
to help address this problem as you plan your strategies for the
year ahead.
A good friend called me the other day. He’s one
of those unfortunates who inherited a tendency for high cholesterol
and he knew that I had had some luck with lowering my cholesterol
with diet. "But, I can’t imagine life without bananas and
potatoes!" he wailed. "Maybe it’s better to have ‘quality’
of life and not worry about the possibility of high cholesterol
causing heart problems?"
I assured him that many of the tenets proposed by
diet gurus were not based on rocket science. Some popular rationales
like the values in the glycemic index were the result of observation
and there was precious little science to back up their claims.
"Think of this as an experiment," I suggested. "Try
making a few changes and see what happens. Everyone is unique.
Everyone has a different approach to eating and exercise. Try a few
things and find out what works for you."
My friend calmed down. I offered, "After you
try a few things for a few months, then see your doctor for another
test, say six months from now. When you get the results, you’ll
know more about what works for you and you can decide what the next
steps will be."
He was obviously much happier than when he
called. "OK! Maybe I don’t need a banana every day and I do
like blueberries, so I’ll try it out! I’ll let you know how
things go!"
"Great!" I said, "Stay in
touch!"
After our phone conversation, I remarked to
myself that it was amazing how little it had taken on my part to
move my friend from panic and resistance to a calm, accepting state.
What I had applied was an influence strategy that has been captured
as one of a collection of patterns to appear in a book that Mary
Lynn Manns and I are writing. The book will appear in September of
this year. The working title is "Fear Less: Patterns anyone can
use to introduce new ideas." I have written some articles for
this on-line publication on these patterns and influence strategies
(See The DDC-I Online
News Archive). This particular pattern is a relatively new
one and is worth some extra explanation.
The pattern is called "Trial Run." Why
is it such a valuable strategy? Because most of the time, for most
of us, change is difficult. It’s especially difficult when our
jobs are threatened in these tough economic times. It’s really,
really difficult when it means giving up something that is a
highlight in our day, that special dessert, for instance! Even when
we rationally know that improving our skills or watching our diet is
good and good for us, we resist making changes. When we see the
change as "temporary," the new approach suddenly becomes
less of a threat. We are less resistant and more open, when we think
of the change as an experiment, just something we’re going to try
on for size.
Trialability has been identified as an important
component in making innovation more appealing. Whenever possible,
introduce a new approach with a "Trial Run," just like a
test drive for a car. You know, try it out, if you don’t like it
you can bring it back, no questions asked, no problem! Money-back
guarantee! It makes us more open to the new approach. We are less
resistant to considering having anything to do with the new thing if
we can somehow believe we’re just trying it on for size.
To enhance the strategy, introduce an unexpected
or unusual variation. This also lowers resistance. In a recent
experiment, students posing as beggars found that they received
small change 44% of the time when they didn’t specify a sum. If
they asked for a precise sum that was a single coin (25 cents), they
got it 64% of the time. But if they asked for an apparently
arbitrary number (37 cents) they got it 75% of the time. The more
unusual the request, the more likely it was to be satisfied.
In your suggestion for a "Trial Run" of
a new idea, you might give a specific and unexpected variation on
the "let’s try it" approach. For instance, you might
say, "Let’s try it for a week and a half and then see how
things are going." The brain loves to whirl around on complex
instructions like "a week and a half." Turning
possibilities around in their minds keeps vocal skeptics busy, while
plans are being made for the experiment. Since no objections were
heard, you have a chance to get things off the ground.
Once the experiment has been launched, make sure
you don’t try to take on too much. This is the pattern called
"Step by Step." Those of us who are change agents are
usually so enthusiastic about our new idea that we want to change
the world overnight. The best approach, however, is always a gradual
one. It took the military 75 years to go from muskets to rifles.
This makes the 15 years it typically takes for new software
technologies to be accepted seem like a short time!
Col. David Hackworth writes in his compelling
account, Steel My Soldiers’ Hearts, as a change agent in
Vietnam:
Some command principles are just common sense.
Good small-unit leaders make for good battalions, so I fired two
small-unit leaders and replaced them with my men. A thousand other
changes needed to be made, but I didn’t want to bury my staff on
our first day together. If I’d ordered all shortcomings squared
away immediately, I’d have sent them into overload. I approached
the conversion the same way I’d train a pup. Just a few tricks
at a time. "Starting now, we’re going to follow the
two-rule plan," I said. "I’ll tell you what the two
new rules are and you’ll make them happen. Once your troops have
mastered the first two rules, we’ll add two more and we’ll
keep doing that until we’re squared away. First we’ll crawl,
then we’ll walk and then we’ll run. Just stay with me—because
we’re going to run faster and faster every day."
As Seth Godin observed in a recent Fast
Company article, "Slowly I Turned:"
If every element of an organization gets a
little better every day, then that organization will become
unstoppable. An organization that builds that kind of momentum
will soon evolve into a market leader. Yet our impatience negates
the simplicity of that statement. Amazingly, it was the Three
Stooges who first codified this management technique: "Slowly
I turned . . . step by step . . . inch by inch . . ." It
worked for them, and it can work for us. We're not going to fix
our economy -- or our miserable negative attitude -- with a
federally mandated intervention in time for the next election.
You're not going to build a great company because of a neat idea
that you got in the shower one day. You're not going to find that
perfect job just because your resume ends up on the right desk on
the right day. We need to stop shopping for lightning bolts. The
way out of our paralysis is simpler than that: It's about thinking
small and thinking gradual.
The work of introducing a new idea really never
ends. There are always new people to bring in and new management to
sell. However, after awhile you’ll see that time has joined your
side as a result of inertia and momentum. There is a natural
tendency to continue effort. This tends to work against you in the
beginning but the latter momentum will be working for you. Just as
it was difficult to get things going, it’s difficult to stop them
once they are in motion. If you just do something small every day,
with experiment being your primary mode of operation, you’ll reach
a state of "Sustained Momentum" – another pattern and
enlist inertia in the battle to introduce your new idea.
And the best way to get things going? Have a
"Trial Run" or a test drive. How should you proceed?
Slowly, "Step by Step." And your goal? "Sustained
Momentum!"
If you have stories to share about how you
introduced a new idea into your organization, I would love to hear
them! Thanks for reading!
 |
About the Author
http://www.lindarising.org
risingl@acm.org
Linda Rising has a Ph.D. from Arizona
State University in the area of object-based design metrics.
Her background includes university teaching as well as work
in industry in telecommunications, avionics, and strategic
weapons systems. She is the author of numerous articles and
has published three books: Design Patterns in
Communications, The Pattern Almanac 2000, and A Patterns
Handbook. She is currently writing a book with Mary Lynn
Manns: Introducing Patterns (or any Innovation) into
Organizations, to appear in 2004. |
[
Back to Top ]
|
