Velocity Reviews > bit vector question: why shift (>>) 5?

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

gokkog@yahoo.com
Guest
Posts: n/a

 09-16-2006
Hello,

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 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?

Some references to bit vector tutorials are also welcome.

Thanks and best regards,
Wenjie

Bill Pursell
Guest
Posts: n/a

 09-16-2006

http://www.velocityreviews.com/forums/(E-Mail Removed) 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 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?" This would be much more clearly written as:
void set(int i) { a [ i / BITSPERWORD ] |= (1 << ( i % BITSPERWORD));}

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.)

And BITSPERWORD would be better defined as
#define BITSPERWORD ( sizeof (int) * CHAR_BIT)

--
Bill Pursell

Jean-Marc Bourguet
Guest
Posts: n/a

 09-16-2006
"Bill Pursell" <(E-Mail Removed)> writes:

> (E-Mail Removed) 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 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.

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

Yours,

--
Jean-Marc

gokkog@yahoo.com
Guest
Posts: n/a

 09-17-2006
Jean-Marc Bourguet wrote:
> "Bill Pursell" <(E-Mail Removed)> writes:
>
> > (E-Mail Removed) 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 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
> >
> > 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

CBFalconer
Guest
Posts: n/a

 09-17-2006
(E-Mail Removed) wrote:
>

.... snip ...
>
> 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

>From N869:

6.5.7 Bitwise shift operators

Syntax

[#1]
shift-expr:

Constraints

[#2] Each of the operands shall have integer type.

Semantics

.... snip ...

[#4] The result of E1 << E2 is E1 left-shifted E2 bit
positions; vacated bits are filled with zeros. If E1 has an
unsigned type, the value of the result is E1+2E2, reduced
modulo one more than the maximum value representable in the
result type. If E1 has a signed type and nonnegative value,
and E1+2E2 is representable in the result type, then that is
the resulting value; otherwise, the behavior is undefined.

[#5] The result of E1 >> E2 is E1 right-shifted E2 bit
positions. If E1 has an unsigned type or if E1 has a signed
type and a nonnegative value, the value of the result is the
integral part of the quotient of E1 divided by the quantity,
2 raised to the power E2. If E1 has a signed type and a
negative value, the resulting value is implementation-
defined.

i.e. for negative values the results are not portable. So don't do
that. The phrase "2E2" above is a result of the conversion to
text, and means 2 to the E2 power.

--

"The most amazing achievement of the computer software industry
is its continuing cancellation of the steady and staggering
gains made by the computer hardware industry..." - Petroski

--
Posted via a free Usenet account from http://www.teranews.com

Jean-Marc Bourguet
Guest
Posts: n/a

 09-17-2006
(E-Mail Removed) writes:

>> 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.

That don't say how important the rewriting has been. It could have been
just adding the return type of main and prototypes. It could have been
more important. Even if the rewriting has been more important, when you
have something under your eyes, you are influenced by it.

>> > This would be much more clearly written as: void set(int i) { a [ i /
>> > BITSPERWORD ] |= (1 << ( i % BITSPERWORD));} etc. That should answer
>> >
>> > 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?

Shifting a negative value is undefined or implementation defined behaviour
(depending on the direction, see CBFalconer post), so most implementations
will not do something special to handle those cases while still trying to
meet the expectations of people knowing the target architecture.

Most two's complement machines have an arithmetic right shift which keep
the sign and I expect most C compiler for those machines will use it when
shifting signed int. The result is that, on those machine right shifting
is a division truncated towards minus infinity while C99 standard demand
that division is truncated towards zero. So few compiler will generate the
same code for a right shift of a signed int and for a division.

To do the right thing for bit vector, the first thing to do is to modify
the declaration and allocation of a so that negative indexes are possible.
That done, it seems to me that Jon Bentley's version will do the right
thing on most two's complement machines but that is not demanded by the
standard.

Yours,

--
Jean-Marc

Ben Bacarisse
Guest
Posts: n/a

 09-17-2006
CBFalconer <(E-Mail Removed)> writes:

>>From N869:

> 6.5.7 Bitwise shift operators

<snip>
> [#4] The result of E1 << E2 is E1 left-shifted E2 bit
> positions; vacated bits are filled with zeros. If E1 has an
> unsigned type, the value of the result is E1+2E2, reduced
> modulo one more than the maximum value representable in the

<snip>
> The phrase "2E2" above is a result of the conversion to
> text, and means 2 to the E2 power.

The phrase "E1+" is also, I hope, a result of the conversion since in
my copy of a later draft the plus is, of course, a multiply operation.

--
Ben.

T.M. Sommers
Guest
Posts: n/a

 09-17-2006
Jean-Marc Bourguet wrote:
> (E-Mail Removed) writes:
>
>>>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.

>
> That don't say how important the rewriting has been. It could have been
> just adding the return type of main and prototypes. It could have been
> more important. Even if the rewriting has been more important, when you
> have something under your eyes, you are influenced by it.

The code in question does not exist in the first edition (1986)
of the book.

--
Thomas M. Sommers -- (E-Mail Removed) -- AB2SB