eric@snark.UUCP (Eric S. Raymond) (10/19/87)
In article <148@artsvax.UUCP>, mike@artsvax.UUCP (Michael Czeiszperger) writes: > The variable five is certainly stored in binary, even though it represents > an integer. A more plausible interpretation in a test situation would be > to print each of the binary bits out in ascii, so that the output for an > integer 5 (assuming a large machine where an integer is 4 bytes) would be: > > 00000000000000000000000000000101 I thought about the standard ways to do this, (essentially, crack the sucker into powers-of-two internally via repeated integer-divide and modulo operations) went *ugh*, and then had a flash that gave me an amusing alternate solution. Here it is: (warning! this is untested and off-the-cuff) #include "stdio.h" void bprint(n, fp) /* print n in binary to given fp */ int n; FILE *fp; { static char *nybbles = { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111", }; static char hexdigits = "0123456789abcdef"; char foobuf[BUFSIZ], *cp; /* BUFSIZ from stdio.h */ (void) sprintf(cp = foobuf, "%x", n); while (*cp) (void) fputs(nybbles[strchr(hexdigits, *cp++) - hexdigits], fp); } Le voila! Let the C libraries do the work whenever you can, I always say... -- Eric S. Raymond UUCP: {{seismo,ihnp4,rutgers}!cbmvax,sdcrdcf!burdvax,vu-vlsi}!snark!eric Post: 22 South Warren Avenue, Malvern, PA 19355 Phone: (215)-296-5718
smvorkoetter@watmum.UUCP (10/20/87)
In article <235@snark.UUCP> eric@snark.UUCP (Eric S. Raymond) writes: >I thought about the standard ways to do this, (essentially, crack the sucker >into powers-of-two internally via repeated integer-divide and modulo >operations) went *ugh*, and then had a flash that gave me an amusing >alternate solution. Here it is: (warning! this is untested and off-the-cuff) There is a very quick way to do this using only the <<, >>, and & operators: #define BITS 32 /* or 16 */ void print_binary(n) int n; { int i; for(i = 0; i < BITS; i++) { printf("%1d",(n >> (BITS - 1)) & 1); n <<= 1; } }
mcdonald@uxe.cso.uiuc.edu (10/23/87)
>#include "stdio.h" >void bprint(n, fp) >/* print n in binary to given fp */ >int n; >FILE *fp; >{ > static char *nybbles = > > { > "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", > "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111", > }; > static char hexdigits = "0123456789abcdef"; > > char foobuf[BUFSIZ], *cp; /* BUFSIZ from stdio.h */ > > (void) sprintf(cp = foobuf, "%x", n); > while (*cp) > (void) fputs(nybbles[strchr(hexdigits, *cp++) - hexdigits], fp); >} Arrgh gasp complicated! perhaps (going to stdout, and for longs, but you get the idea): #include <stdio.h> bprint(number) long number; { unsigned long mask; for (mask = ~( (~(unsigned long)1l) >> 1); mask != 0 ; mask >>= 1) putchar((((unsigned long)number & mask) != 0l) + '0'); } On paper this even works on 1's complements machines, although I haven't tried it except on 2's complement. Note that nowhere is the word size explicitly needed. Doug McDonald
hunt@spar.SPAR.SLB.COM (Neil Hunt) (10/23/87)
This is crying out for recursion: /* * print_binary: * Prints `value' in binary with `bits' digits. */ void print_binary(value, bits) int value, bits; { if(--bits > 0) print_binary(value >> 1, bits); putchar((value & 0x1) + '0'); } To print without extra leading zeros or ones (that is if the value is positive, print a single 0 then the actual number, if it is negative, print a single 1 and then the actual number): /* * print_normalised_binary: * Prints `value' in binary with sign bit in normalised position. * Assumes a sign extending '>>'. */ void print_normalised_binary(value) int value; { if(value != 0 && value != -1) print_normalised_binary(value >> 1); putchar((value & 0x1) + '0'); } Exercise 1a: rewrite the above functions for printing hexadecimal and octal Neil/.
bright@dataio.Data-IO.COM (Walter Bright) (10/23/87)
In article <2072@watcgl.waterloo.edu> smvorkoetter@watmum.waterloo.edu (Stefan M. Vorkoetter) writes: >In article <235@snark.UUCP> eric@snark.UUCP (Eric S. Raymond) writes: >>I thought about the standard ways to do this, (essentially, crack the sucker >>into powers-of-two internally via repeated integer-divide and modulo >>operations) went *ugh*, and then had a flash that gave me an amusing >>alternate solution. Here it is: (warning! this is untested and off-the-cuff) > >There is a very quick way to do this using only the <<, >>, and & operators: > >#define BITS 32 /* or 16 */ > >void print_binary(n) >int n; >{ > int i; > > for(i = 0; i < BITS; i++) { > printf("%1d",(n >> (BITS - 1)) & 1); > n <<= 1; > } >} Newsgroups: misc.misc,comp.lang.c Subject: Re: Printing binary (was: Re: Why college?) Summary: Expires: References: <35@ateng.UUCP> <3194@sol.ARPA> <2783@xanth.UUCP> <235@snark.UUCP> <2072@watcgl.waterloo.edu> Sender: Reply-To: bright@dataio.UUCP (Walter Bright) Followup-To: Distribution: Organization: Data I/O Corporation; Redmond, WA Keywords: In article <2072@watcgl.waterloo.edu> smvorkoetter@watmum.waterloo.edu (Stefan M. Vorkoetter) writes: <In article <235@snark.UUCP< eric@snark.UUCP (Eric S. Raymond) writes: <<I thought about the standard ways to do this, (essentially, crack the sucker <<into powers-of-two internally via repeated integer-divide and modulo <<operations) went *ugh*, and then had a flash that gave me an amusing <<alternate solution. Here it is: (warning! this is untested and off-the-cuff) <There is a very quick way to do this using only the <<, >>, and & operators: <#define BITS 32 /* or 16 */ <void print_binary(n) <int n; <{ int i; < for(i = 0; i < BITS; i++) { < printf("%1d",(n >> (BITS - 1)) & 1); < n <<= 1; < } <} I simply modified the printf() format to add a %b format specifier for binary format. It added a case and 1 line of code. Also, things like %04b were gotten for free. I imagine that this is equally trivial for other compilers. Anyone know why ANSI C doesn't specify this? I wrote them a letter which they haven't replied to.
greg@gryphon.CTS.COM (Greg Laskin) (10/25/87)
In article <2072@watcgl.waterloo.edu> smvorkoetter@watmum.waterloo.edu (Stefan M. Vorkoetter) writes: >In article <235@snark.UUCP> eric@snark.UUCP (Eric S. Raymond) writes: >>I thought about the standard ways to do this, (essentially, crack the sucker >>into powers-of-two internally via repeated integer-divide and modulo >>operations) went *ugh*, and then had a flash that gave me an amusing >>alternate solution. Here it is: (warning! this is untested and off-the-cuff) > >There is a very quick way to do this using only the <<, >>, and & operators: > >#define BITS 32 /* or 16 */ > >void print_binary(n) >int n; >{ > int i; > > for(i = 0; i < BITS; i++) { > printf("%1d",(n >> (BITS - 1)) & 1); ^^^^^^^^^^^^^^^ not a constant expression > n <<= 1; > } >} #define BitsPerUnit 8 void print_binary(n) int n; { int i; for (i=0; i < (sizeof (int) * BitsPerUnit) ; ++i,n<<=1) putchar(( n & (1<<(sizeof (int) * BitsPerUnit) -1)) ? '1' : '0'); /* a constant expression */ } Using the constant expression is "quick"er. On my 16 bit machine, the compiler can resolve the expression to: putchar((n & 0x8000 ) ? '1' : '0'); at compile time instead of shifting n BITS bits BITS times at run time. Using putchar() instead of printf() is picking a nit. Comments on portability to other environments solicited (by email please). -- Greg Laskin "When everybody's talking and nobody's listening, how can we decide?" INTERNET: Greg.Laskin@gryphon.CTS.COM UUCP: {hplabs!hp-sdd, sdcsvax, ihnp4}!crash!gryphon!greg UUCP: {philabs, scgvaxd}!cadovax!gryphon!greg
eric@snark.UUCP (Eric S. Raymond) (10/25/87)
In article <1646@spar.SPAR.SLB.COM>, hunt@spar.SPAR.SLB.COM (Neil Hunt) writes: > This is crying out for recursion: [followed by a print_binary implementation] Now that's more elegant than my internal-to-hex-nybbles-to binary hack (which I posted mostly for its giggle value). It also avoids the flaw of the second proposal (which is nonportable, requiring this ugly #define in source for the machine's word length). But your trick can't be generalized to do the sprintf analogue. GONG! :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-) :-)
greg@gryphon.CTS.COM (Greg Laskin) (10/26/87)
In article <1646@spar.SPAR.SLB.COM> hunt@spar.UUCP (Neil Hunt) writes: >This is crying out for recursion: > void > print_binary(value, bits) > int value, bits; > { > if(--bits > 0) > print_binary(value >> 1, bits); > putchar((value & 0x1) + '0'); > } > Why would this cry out to incur the additional overhead of recursion just to flip the order of the bits around when you could easily pick the bits off the left side and use a simple loop to do the job? Pretty algorithm though. -- Greg Laskin "When everybody's talking and nobody's listening, how can we decide?" INTERNET: Greg.Laskin@gryphon.CTS.COM UUCP: {hplabs!hp-sdd, sdcsvax, ihnp4}!crash!gryphon!greg UUCP: {philabs, scgvaxd}!cadovax!gryphon!greg
hunt@spar.SPAR.SLB.COM (Neil Hunt) (10/26/87)
In article <2034@gryphon.CTS.COM> greg@gryphon.CTS.COM (Greg Laskin) writes: >In article <1646@spar.SPAR.SLB.COM> hunt@spar.UUCP (Neil Hunt) writes: >>This is crying out for recursion: >> void >> print_binary(value, bits) >> int value, bits; >> { >> if(--bits > 0) >> print_binary(value >> 1, bits); >> putchar((value & 0x1) + '0'); >> } >> >Why would this cry out to incur the additional overhead of recursion >just to flip the order of the bits around when you could easily pick >the bits off the left side and use a simple loop to do the job? I knew that someone would ask this. Check out all the stuff that has to happen to get the binary bits displayed on the screen, or written to a file, and see if building a new stack frame 31 times is a significant penalty. One of the basic rules about writing code is only to sacrifice clarity for efficiency when it will make a difference ! > >Pretty algorithm though. Thankyou ! Neil/.
gwyn@brl-smoke.ARPA (Doug Gwyn ) (10/27/87)
In article <1398@dataio.Data-IO.COM> bright@dataio.UUCP (Walter Bright) writes: >I simply modified the printf() format to add a %b format specifier for >binary format. ... >Anyone know why ANSI C doesn't specify this? I wrote them a letter which >they haven't replied to. The replies to comments received during the first formal public review are being edited into a response document and should be mailed to the correspondents within the next couple of months. My notes show that any comment you had about %b was not included in your formal comments, however. Responses to informal letters from the public are less complete than the official review responses; some have already been sent to correspondents and others may be soon, but due to shortage of manpower some unofficial comments may simply not get replied to. We'll reply to as many as we can. Generally, for ideas such as %b, you may assume that if the Committee did not adopt it for the Standard, it was mainly because the necessity for extending widespread existing practice was not convincingly shown. There must have been literally over a thousand suggestions for new features, any one of which might seem benign, but the total weight of adopting all equally valuable inventions would have been crushing. I personally would have preferred a degrees/minutes/seconds floating conversion to a binary integer conversion, but I didn't press for it. While the above is not an official X3J11 opinion, as editor of the response document I'm fairly sure it's accurate.
chris@mimsy.UUCP (Chris Torek) (10/27/87)
In article <1668@spar.SPAR.SLB.COM> hunt@spar.SPAR.SLB.COM (Neil Hunt) writes, in response to a question about efficiency: >Check out all the stuff that has to happen to get the binary bits >displayed on the screen, or written to a file, and see if building >a new stack frame 31 times is a significant penalty. On a Vax 11/780, yes. putchar (of other than '\n') expands to 5 instructions n-1 out of n times, where n is the amount of buffering on a stdio stream; the loop and test expand to 3 more. A call-and-return on a 780 takes about 12 times longer than the `average' instruction. Hence if you are printing a very large number of binary numbers, the recursive routine will take more than twice as long user-time-wise. As another metric, the `average' 4.3BSD program uses a bit more user time than system time. Of course, you are probably printing very few binary numbers; and you are probably not using a machine with as heavy a call+return penalty as a 780. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7690) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
mcdonald@uxe.cso.uiuc.edu.UUCP (10/27/87)
********this is a repost***** ********the notes system bounced this with a message about "network congestion" has this happened to you?*********** >#include "stdio.h" >void bprint(n, fp) >/* print n in binary to given fp */ >int n; >FILE *fp; >{ > static char *nybbles = > > { > "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", > "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111", > }; > static char hexdigits = "0123456789abcdef"; > > char foobuf[BUFSIZ], *cp; /* BUFSIZ from stdio.h */ > > (void) sprintf(cp = foobuf, "%x", n); > while (*cp) > (void) fputs(nybbles[strchr(hexdigits, *cp++) - hexdigits], fp); >} Arrgh gasp complicated! perhaps (going to stdout, and for longs, but you get the idea): #include <stdio.h> bprint(number) long number; { unsigned long mask; for (mask = ~( (~(unsigned long)1l) >> 1); mask != 0 ; mask >>= 1) putchar((((unsigned long)number & mask) != 0l) + '0'); } On paper this even works on 1's complements machines, although I haven't tried it except on 2's complement. Note that nowhere is the word size explicitly needed. Doug McDonald
herndon@umn-cs.UUCP (Robert Herndon) (10/28/87)
In article <247@snark.UUCP>, eric@snark.UUCP (Eric S. Raymond) writes: > In article <1646@spar.SPAR.SLB.COM>, hunt@spar.SPAR.SLB.COM (Neil Hunt) writes: > > This is crying out for recursion: [followed by a print_binary implementation] > > Now that's more elegant than my internal-to-hex-nybbles-to binary hack (which > I posted mostly for its giggle value). It also avoids the flaw of the second > proposal (which is nonportable, requiring this ugly #define in source for the > machine's word length). > > But your trick can't be generalized to do the sprintf analogue. GONG! This isn't exactly the ticket, but it shows how it can be done. (This is a library routine I've used for years.) -----------------------------------------------Cut Here. #include <stdio.h> /* * itoa(n, b, s) * Puts base b character representation of n into s, terminates * representation with null. Returns pointer to null at end of * representation. * * Works for n >= 0, 2 <= b <= 32. * Robert Herndon, May 1977. */ char *itoa(n, b, s) int n, b; char *s; { if(n/b != 0) { s = itoa(n/b, b, s); } *s++ = "0123456789ABCDEFGHIJKLMNOPQRSTUV"[n%b]; *s = '\0'; return s; } main(ac, av) int ac; char *av[]; { char result[50]; if(ac < 3) { fprintf(stderr, "Usage: itoa <number> <base>"); exit(1); } itoa(atoi(av[1]), atoi(av[2]), result); printf("%s(10) = %s(%s)\n", av[1], result, av[2]); } -- Robert Herndon Dept. of Computer Science, ...!ihnp4!umn-cs!herndon Univ. of Minnesota, herndon@umn-cs.ARPA 136 Lind Hall, 207 Church St. SE herndon.umn-cs@csnet-relay.ARPA Minneapolis, MN 55455
mwlcs423@nmtsun.UUCP (10/28/87)
[Really neat recursive function omited] > One of the > basic rules about writing code is only to sacrifice clarity for efficiency > when it will make a difference ! I agree 100 percent. Too many people think that 1ns of speed saving is worth it. Keep it clear!!! That is the most important thing in ALL coding, not to save 1ns of time. > > > > >Pretty algorithm though. > Yes it is. Warner
greg@gryphon.UUCP (10/28/87)
In article <1668@spar.SPAR.SLB.COM> hunt@spar.UUCP (Neil Hunt) writes: >In article <2034@gryphon.CTS.COM> greg@gryphon.CTS.COM (Greg Laskin) writes: >>In article <1646@spar.SPAR.SLB.COM> hunt@spar.UUCP (Neil Hunt) writes: >>>This is crying out for recursion: >>> [ recursive solution deleted] >>Why would this cry out to [ recurse ...] > >I knew that someone would ask this. Check out all the stuff that has to happen >to get the binary bits displayed on the screen, or written to a file, and see >if building a new stack frame 31 times is a significant penalty. One of the >basic rules about writing code is only to sacrifice clarity for efficiency >when it will make a difference ! Objectively, the performance penalty is 15-30% (16 bitties on my 286 -- benchmarks available on request) against the recursive solution depending on whether run-time stack checking is performed. Results might/would vary depending on many machine dependent variables. Subjectively, the clarity vs. efficiency question is, in this rather trivial case, probably a matter for the profiler to sort out. Here "all the stuff that has to happen" is relatively small compared to the recursion overhead. More complex "stuff" would flatten out the differences, of course. It's all academic anyway. -- Greg Laskin "When everybody's talking and nobody's listening, how can we decide?" INTERNET: Greg.Laskin@gryphon.CTS.COM UUCP: {hplabs!hp-sdd, sdcsvax, ihnp4}!crash!gryphon!greg UUCP: {philabs, scgvaxd}!cadovax!gryphon!greg
gwyn@brl-smoke.ARPA (Doug Gwyn ) (10/30/87)
In article <949@nmtsun.nmt.edu> mwlcs423@nmtsun.nmt.edu (M. Warner Losh) writes: >> >Pretty algorithm though. >Yes it is. Not to detract from the referenced algorithm, but I thought it might be worth noting that we used to implement it as something like three lines of MACRO-10 (the PDP-10 assembly language), including the monitor call to print a character.