wirthlin@uvm-gen.UUCP (Ralph Wirthlin) (04/04/89)
This may have already been asked, but ... Does anyone know of a *very fast* way to swap bits at some location n between two separate bytes b1 and b2? offset 3 2 1 0 ======= e.g. b1 -> 0 0 1 1 b2 -> 1 0 1 0 swapping bits at offset 3 would produce offset 3 2 1 0 ======= b1 -> 1 0 1 1 b2 -> 0 0 1 0 Thanks for any help you can give. ------------------------------------------------------------------------------- Ralph L. Wirthlin | "Who knows where madness lies .. EMAIL:wirthlin@uvm-gen.uvm.edu | To surrender dreams, this may be USMAIL: BOX 125 Newport Ctr., VT | madness .. too much sanity is madness, | but maddest of all is to see life as | it is and not as it should be" | - Man of La Mancha -------------------------------------------------------------------------------
gwyn@smoke.BRL.MIL (Doug Gwyn ) (04/04/89)
In article <1138@uvm-gen.UUCP> wirthlin@uvm-gen.UUCP (Ralph Wirthlin) writes: >Does anyone know of a *very fast* way to swap bits at some location n >between two separate bytes b1 and b2? The answer must of course depend on architectural and language implementation details. One very fast way is to directly index the result in a table a la b1_swapped = b_table[b1][b2][offset]; b2_swapped = b_table[b2][b1][offset]; where of course the tables have been preinitialized with the correct answers. If you don't have space for such a large table (512Kbytes, assuming 8-bit bytes) then a compromise solution that generally takes longer but uses a tiny table is b1_bit = b1 & mask[offset]; b2_bit = b2 & mask[offset]; b1 = b1 & ~mask[offset] | b2_bit; b2 = b2 & ~mask[offset] | b1_bit; with suitable optimization. If your processor has a very speedy shift operator then replace mask[offset] with (1<<offset), but first check that 1<<0 works (I once ran into a processor where it didn't).
trt@rti.UUCP (Thomas Truscott) (04/04/89)
> Does anyone know of a *very fast* way to swap bits at some location n > between two separate bytes b1 and b2? Suppose "mask" is a mask of the bits you want swapped (e.g. to swap the 3rd (4-valued) bit the mask would be 0x04). Then the following will swap the "mask"ed bits of b1 and b2: t = (b1 ^ b2) & mask; b1 ^= t; b2 ^= t; Depending on your machine this may be faster than any table lookup. Of course *very fast* means you should (a) scrutinize the compiler's assembly output and (b) ponder your machine's instruction set repertoire to ensure you are not wasting cycles. (E.g. does your machine have an XOR instruction? Is it a fast instruction? How should "t" be declared? Do you need to declare it "register"? Which is faster, "& mask" or "& ~mask"? And so on.) Tom Truscott
rbj@dsys.icst.nbs.gov (Root Boy Jim) (04/04/89)
? From: Ralph Wirthlin <wirthlin@uvm-gen.uucp>
? Keywords: bits, flip
? This may have already been asked, but ...
? Does anyone know of a *very fast* way to swap bits at some location n
? between two separate bytes b1 and b2?
? offset
? 3 2 1 0
? =======
? e.g. b1 -> 0 0 1 1
? b2 -> 1 0 1 0
?
? swapping bits at offset 3 would produce
? offset
? 3 2 1 0
? =======
? b1 -> 1 0 1 1
? b2 -> 0 0 1 0
void bit flip(x,y,mask) int *x, *y; /* mask can be more than one bit */
{
int z = (x ^ y) & mask; /* difference of interesting bits */
if (z) /* some bits differ */
x ^= z, y^= z; /* flip those that do */
}
? Ralph L. Wirthlin
? EMAIL:wirthlin@uvm-gen.uvm.edu
? USMAIL: BOX 125 Newport Ctr., VT
Catman Rshd <rbj@nav.icst.nbs.gov>
Author of "The Daemonic Versions"sl@van-bc.UUCP (pri=-10 Stuart Lynne) (04/05/89)
In article <1138@uvm-gen.UUCP> wirthlin@uvm-gen.UUCP (Ralph Wirthlin) writes: >Does anyone know of a *very fast* way to swap bits at some location n >between two separate bytes b1 and b2? For fast generic swapping I use: #define swap(a,b) {a^=b;b^=a;a^= b;} This method has the advantage of not needing any temporary variable. So if your arg's are in registers it reduces to three XOR instructions. Be sure to implement as a macro, procedure call overhead would dwarf everything else if you didn't. Adding masks so that it only handles bits is left as an exercise for the reader :-) -- Stuart.Lynne@wimsey.bc.ca uunet!van-bc!sl 604-937-7532(voice) 604-939-4768(fax)
daveb@gonzo.UUCP (Dave Brower) (04/07/89)
In article <18944@adm.BRL.MIL> a unidentified co-conspirator says: > >void bit flip(x,y,mask) int *x, *y; /* mask can be more than one bit */ >{ > int z = (x ^ y) & mask; /* difference of interesting bits */ > if (z) /* some bits differ */ > x ^= z, y^= z; /* flip those that do */ >} I say, dear netters, that this use of the comma operator is an abomination, and we should fear for any freshmen who come upon it as an example of the sort of thing they ought to be writing. Rather: int z = (x ^ y) & mask; /* difference of interesting bits */ if (z) { /* some bits differ */ x ^= z; /* flip those that do */ y^= z; } If you don't see _why_ this is the right way, you'd better not work on a project with anyone but yourself. -dB -- "I came here for an argument." "Oh. This is getting hit on the head" {sun,mtxinu,amdahl,hoptoad}!rtech!gonzo!daveb daveb@gonzo.uucp
gwyn@smoke.BRL.MIL (Doug Gwyn ) (04/08/89)
In article <626@gonzo.UUCP> daveb@gonzo.UUCP (Dave Brower) writes: >> x ^= z, y^= z; /* flip those that do */ - x ^= z; /* flip those that do */ - y^= z; -If you don't see _why_ this is the right way, you'd better not work on a -project with anyone but yourself. Hey, now, it's not all that clear cut. Conceptually the two assignments should occur in parallel; for some people using , to separate such assignments is the "natural" way to express that.
dg@lakart.UUCP (David Goodenough) (04/10/89)
From article <2345@van-bc.UUCP>, by sl@van-bc.UUCP (pri=-10 Stuart Lynne): > In article <1138@uvm-gen.UUCP> wirthlin@uvm-gen.UUCP (Ralph Wirthlin) writes: >>Does anyone know of a *very fast* way to swap bits at some location n >>between two separate bytes b1 and b2? > > For fast generic swapping I use: > > #define swap(a,b) {a^=b;b^=a;a^= b;} I think Mr. Wirthlin is after something that will leave all bits alone, except it will swap (for example) bit 2 between the bytes. I submit the following extension to Mr. Lynne's macro: #define swap(a, b, n) ((a) ^= ((b) & (n)), (b) ^= ((a) & (n)), \ (a) ^= ((b) & (n))) where n is a mask of bits to be swapped. This can also be used in expressions returning the final value of a. Of course if you want to explicitly swap bit 2 or bit 5, i.e. give the bit by number: #define swapn(a, b, x) swap((a), (a), (1 << (x))) -- dg@lakart.UUCP - David Goodenough +---+ IHS | +-+-+ ....... !harvard!xait!lakart!dg +-+-+ | AKA: dg%lakart.uucp@xait.xerox.com +---+
rbj@dsys.icst.nbs.gov (Root Boy Jim) (04/12/89)
? From: Doug Gwyn <gwyn@smoke.brl.mil>
? In article <626@gonzo.UUCP> daveb@gonzo.UUCP (Dave Brower) writes:
? RBJ>> x ^= z, y^= z; /* flip those that do */
? - x ^= z; /* flip those that do */
? - y^= z;
? -If you don't see _why_ this is the right way, you'd better not work on a
? -project with anyone but yourself.
? Hey, now, it's not all that clear cut. Conceptually the two
? assignments should occur in parallel; for some people using , to
? separate such assignments is the "natural" way to express that.
Yeah, but unless ANSI changed the meaning of ",", they evaluate
left to right. I stand by my original use of the comma operator.
Some people may not like it, but it's legal C. Some people go
so far as to write "if (z != 0)" instead of "if (z)". This used to
bother me, but it's really a matter of style/religion.
To make Dave Brower really barf, I've started writing my simple
if statements as: "condition && statement". Comes from LISP I suppose.
Hey, I gave up the C newsgroup, don't chase me with it.
Root Boy Jim is what I am
Are you what you are or what?leo@philmds.UUCP (Leo de Wit) (04/14/89)
In article <18944@adm.BRL.MIL> rbj@dsys.icst.nbs.gov (Root Boy Jim) writes: [] |void bit flip(x,y,mask) int *x, *y; /* mask can be more than one bit */ |{ | int z = (x ^ y) & mask; /* difference of interesting bits */ | if (z) /* some bits differ */ | x ^= z, y^= z; /* flip those that do */ |} What is this piece of code supposed to do? Since its return type is 'void', one would expect it to dereference its pointer arguments; it doesn't (so in fact it is a pure function, and since it returns nothing, a no-op 8-). Well, probably the x, y in the function body should read *x, *y; and what about renaming 'void bit flip' to 'void bitflip' ? Makes my compiler happier. B.T.W. am I the first one to spot this? Leo.
dg@lakart.UUCP (David Goodenough) (04/14/89)
From article <10007@smoke.BRL.MIL>, by gwyn@smoke.BRL.MIL (Doug Gwyn ): > In article <626@gonzo.UUCP> daveb@gonzo.UUCP (Dave Brower) writes: >>> x ^= z, y^= z; /* flip those that do */ > - x ^= z; /* flip those that do */ > - y^= z; > -If you don't see _why_ this is the right way, you'd better not work on a > -project with anyone but yourself. > > Hey, now, it's not all that clear cut. Conceptually the two > assignments should occur in parallel; for some people using , to > separate such assignments is the "natural" way to express that. In either case, the assignments happen one after the other. As far as I know, C has no equivalent to the BCPL mechanism: a,b := b,a Which is what we were trying to do in the first place :-) I would add that the comma operator has it's place, and there is nothing wrong with saying: #define swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b)) except the ususal caveats about lvalues and side effects. Think what swap(i, getchar()) Would do :-) [Ouch] -- dg@lakart.UUCP - David Goodenough +---+ IHS | +-+-+ ....... !harvard!xait!lakart!dg +-+-+ | AKA: dg%lakart.uucp@xait.xerox.com +---+
rwl@uvacs.cs.Virginia.EDU (Ray Lubinsky) (04/16/89)
In article <626@gonzo.UUCP>, daveb@gonzo.UUCP (Dave Brower) writes: > In article <18944@adm.BRL.MIL> a unidentified co-conspirator says: > > x ^= z, y^= z; /* flip those that do */ > Rather: > x ^= z; /* flip those that do */ > y^= z; > > If you don't see _why_ this is the right way, you'd better not work on a > project with anyone but yourself. Alright -- I'll bite. Why (other than your personal preference) is the former an example of bad coding practice? It's equivalent to the latter. Don't get me wrong. When I write C programs I even put variable declarations one-per-line, so I, too, would prefer to see the latter, but I can't say unequivocally that it is the *right* way. -- | Ray Lubinsky rwl@amber.cs.virginia.edu (Internet) | | rwl@virginia (BITnet) | | Department of Computer Science, ...!uunet!virginia!uvacs!rwl (UUCP) | | University of Virginia (804) 979-6188 (voice) |
gwyn@smoke.BRL.MIL (Doug Gwyn) (04/17/89)
>From article <10007@smoke.BRL.MIL>, by gwyn@smoke.BRL.MIL (Doug Gwyn ): >> Hey, now, it's not all that clear cut. Conceptually the two >> assignments should occur in parallel; for some people using , to >> separate such assignments is the "natural" way to express that. It never ceases to amaze me how people fail to read the words that I put a fair amount of thought into and instead try to explain to me how the C comma operator works. Please believe me when I tell you that I know how the comma operator works. Then go back and see if you can figure out what I was saying. Thanks.
daveb@gonzo.UUCP (Dave Brower) (04/18/89)
I posted a provocative note, the gist of which was that
if( cond )
e1, e2;
was rotten C programming practice for multiple person projects. Some
people think that is personal preference on my part. Of course I
disagree, and I'll attempt to explain why below.
My "red cape in front of a bull" chemistry produced this retort, which
I'll print and put on my "code from hell" board. Even though I program
exactly that way in /bin/sh, it is not good C for the same reasons the
comma code above makes me ralph.
"To make Dave Brower really barf, I've started writing my simple if
statements as: "condition && statement". Comes from LISP I suppose."
[Instant rebuttal: Everybody writes lisp that way, so it's OK lisp.
How does everybody write C?]
The issue is not absolute code correctness. I will cede that any of
these methods is functionally equivalent to a compiler. The issue is
human intelligibility, which is a different issue. How will people
other than the original author support and maintain this code months and
years after it is released?
I assert that 99 out of 100 competent C programmers write the
same piece of code as the braced, multiple statement sequence:
if( cond ) { /* brace placement left as religious discussion */
e1;
e2;
}
So, I claim 99 out of 100 competent C programmers reading this code
years from now are going to suffer cognitive dissonance on a "comma-ed"
construct when they come upon it. What does the author get from using a
comma? Internal ego strokes for demonstrating once again what a "hot
coder" can do to be obscure while still being correct. Does it enhance
the readability of the code? Not to anyone expecting braces, even the
author 6 months from now. So 99% of the programmers reading this code
will need to spend 5 extra seconds thinking about that line wondering
what is going on because it was not the obvious thing they have come to
expect.
If it is not obvious the program is not communicating its intent to the
human audience very well. That is not good programming, even if it is
"correct."
The comma operator is rarely used in practice, because the real C idiom
is to use braced statments. There are a few cases where it is
approriate, for(;;) loop setup and iteration and in macros that need to
evaluate to a particular value.
Only a raging egomaniac will go out of his way to obscure his code by
using a comma operator elsewhere, even if it "works just fine." Given a
choice between two constructs with equivalent semantics and performance,
the good programmer is going to pick the one more readily understood by
average people reading the code.
If you are working alone, go ahead to write that program that will make
the world believe that obscure feature X is the cat's meow. Just don't
do it in that module you are sharing with 99 other programmers, for
which you are receiving a professional's compensation.
Practically speaking,
-dB
--
"An expert is someone who's right 75% of the time"
{sun,mtxinu,amdahl,hoptoad}!rtech!gonzo!daveb daveb@gonzo.uucp