Re: bit vector question: why shift (>>) 5?

Jean-Marc Bourguet wrote:
"Bill Pursell" <bill.pursell@xxxxxxxxx> writes:

gokkog@xxxxxxxxx wrote:

Recently I have the book Programming Pearls. Nice read! Perhaps it is
weekend, I cannot understand the following codes well:
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + N/BITSPERWORD];

void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); }
void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); }
int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }

From http://netlib.bell-labs.com/cm/cs/pearls/bitsort.c

Why Jon #define SHIFT 5? (and #define MASK 0x1F)? Are there any
differences if I define SHIFT as 3? How about 8?

Are you sure this is "Programming Pearls" and not "Introduction
to Obfuscation?"

Note that the book was first published in the mid 80's and a collection of
columns published before. I don't know how much it has been revised in the
recent printings/editions.

I am reading the second edition (1999), according to the author, all
the example codes have been re-written.


This would be much more clearly written as: void set(int i) { a [ i /
BITSPERWORD ] |= (1 << ( i % BITSPERWORD));} etc. That should answer
your questions.

There are arguments that using the << operater will lead
to better code, but it's highly questionable. (Most compilers
will generate exactly the same code for the two.)

I don't think so (note: i is an *signed* int).

You are talking about specifically "<< as in (1<<...)" not ">> as in
a[i>>SHIFT]"? I tried both versions (Bill Pursell & Jon Bentley),
neither of them handles minus numbers correctly. So what is behind your
hint?


My thanks to all of you.
Wenjie

.

Relevant Pages

  • Re: 97 Blazer 4X4 ECT problem(update)
    ... but how did you get the meaning of those codes off Google? ... about other shift solenoids, as well as the TCC one? ... or maybe the torque convertor started ...
    (sci.electronics.repair)
  • Re: A vs B query?
    ... My SQL to get me the sum of all Direct hours by shift: ... Jessa Lillge ... direct vs. indirect in each of the categories. ... telling the query to remove the codes for indirect work from the results ...
    (microsoft.public.access.queries)
  • Re: Macros/VBA to fill time card
    ... Employees ... select the appropriate cell ... then click the button for the shift that they want. ... > Nightshift, dayshift, holidays, etc. all require different pay codes. ...
    (microsoft.public.excel.programming)
  • Re: Counting current form
    ... Assuming the codes are in the same row ... needs to be entered with ctrl + shift & enter ... Peo Sjoblom ...
    (microsoft.public.excel.misc)
  • bit vector question: why shift (>>) 5?
    ... Recently I have the book Programming Pearls. ... I cannot understand the following codes well: ... #define BITSPERWORD 32 ... differences if I define SHIFT as 3? ...
    (comp.lang.c)