在smth看到有人在讨论”Duff’s Device”,有点疑惑，就google了一下，看到一个台湾的国中生的blog:國二菜鳥忙裡偷閒(btw: 好像是个小愤青，不喜欢编程的也可以区逛逛，:P )引用如下：
/************************************/
这就是神迹 !! 这就是艺术 !!
请各位看看下面这段 code：
register n = (count + 7) / 8; /* count > 0 assumed */
switch (count % 8)
{
case 0: do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
我印象中我在某本书看过这段 code，但是先前当我想要介给别人看的时候突然找不到是在哪本书看过，翻遍了家里的 C 语言相关书籍都没看到，让我有点失落；不过，刚刚在机缘巧合的情况下，我从我的 bookmark 里面找到了 “Steve’s ‘Cute Code’ collection” 这个站，最下面一则赫然就是这段 code !! 原来它的名字叫做 “Duff’s Device”，在 Jargon File 里面有一段 解说，网路上也可以找到本人现身说法，从第 3 点里面我才知道，原来是 BS 兄的书啊… 难怪我猛找 C 的书没有结果 :~
Technorati Tags: programming, jargon
/************************************/
其中，Steve Baker 的网站收集了好多很漂亮的code，另外， 他也是一个很有趣的人，他称Steve's Mini Cooper-S(Yoda - Small, Green and Suprisingly Powerful)
/************************************************/
Steve's 'Cute Code' collection.
Here is my collection of cute C and C++ tricks - I have tried to stick with code that is actually faster or more compact than the conventional way of doing things - or maybe the code just has to look pretty on the page - but this a personal collection, so I get to break the rules if I feel like it!
Unless I indicate otherwise, all variables are unsigned 32 bit integers.
Reverse all the bits in a 32 bit word:
I found this one in the Linux fortune cookie program (!)
n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa) ;
n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc) ;
n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0) ;
n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00) ;
n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000) ;
You can easily make versions of this for other word sizes.
Count the number of '1' bits in a 32 bit word:
John C. Wren &[email protected]> kindly sent me this one. It looks amazingly similar to the previous trick for bit reversal.
n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);
Test to see if a number is an exact power of two:
b = ((n&(n-1))==0) ;
(NB: This code sets 'b' to TRUE if 'n' is an integer power of two - in this context, both zero and one are considered to be powers of two.)
This code actually works by changing the least significant '1' bit of 'n' to a '0'. If 'n' is a power of two, it only has one '1' bit - and zeroing it leaves you with zero as the answer.
Hence, the inner expression is also a cute trick...
Zero the least significant '1' bit in a word.
n&(n-1)
Set the least significant N bits in a word.
~(~0<<n)
Swap the values of two integers.
This one is cute because it doesn't use a temporary variable and it's harder to get wrong than the usual code. It's been around for years, so I have no idea who invented it.
x = x ^ y ;
y = x ^ y ;
x = x ^ y ;
[ The '^' operator stand for 'bitwise XOR' in C/C++ - not 'to the power of' as ex-FORTRAN people seem to think!]
However Scott Smith <[email protected]> pointed out that this is equivelent to the even more aesthetically pleasing:
x ^= y ^= x ^= y ;
It has been pointed out that this is strictly illegal C++ since the same variable is modified twice in one statement.
Convert a nibble into an ASCII hex digit.
Another ancient one. I think I first saw it in the sources for 'vi', but it's probably a lot older than that.
"0123456789ABCDEF" [ n ]
(Where 'n' is in the range 0..15).
I have also seen this:
n [ "0123456789ABCDEF" ]
...which also works providing 'n' is a character variable and providing you turn off enough compiler error checking!
Force all non-zero values to 1.
Pat Down sent me this one:
b = !!a ;
b = 0 if a was 0 otherwise b = 1.
Little-Endian or Big-Endian?
Some computers store integers with the most significant data in the first byte and the least significant data in the last, others do it the other way around. The former type are called 'big-endian' and the latter 'little-endian'. Intel computers are traditionally little-endian and most others big-endian.
Most people do not realise that the terms 'big-endian' and 'little-endian' come from Gulliver's Travels. The nations of Lilliput and Blefuscu were waging a terrible and bloody war over which end one should cut open on a boiled egg - the little end or the big end.
The war between CPU manufacturers is just as silly - and also pretty damaging.
Gulliver says: "...all true Believers shall break their Eggs at the convenient End: and which is the convenient End, seems, in my humble Opinion, to be left to every Man's Conscience, or at least in the power of the Chief Magistrate to determine."
Hmmmm.
Anyway, the way to decide which kind of machine you have is:
int i = 1 ;
little_endian = *((char *) &i ) ;
Duffs Device
No collection would be complete without this:
int a = some_number ;
int n = ( a + 4 ) / 5 ;
switch ( a % 5 )
{
case 0: do
{
putchar ( '*' ) ;
case 4: putchar ( '*' ) ;
case 3: putchar ( '*' ) ;
case 2: putchar ( '*' ) ;
case 1: putchar ( '*' ) ;
} while ( --n ) ;
}
printf ( "n" ) ;
The loop prints the 'a' asterisks - but is 'unrolled' (which is important for speed in some applications). Most people are suprised that this even compiles.
It has been said that the worst problem with Duff's device is knowing how to indent it!
If you have any more good examples for my collection, you can email me at: [email protected]
/********************************************************/
今天写累了 明天再写
hoho