473,721 Members | 1,956 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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

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

Some references to bit vector tutorials are also welcome.
Thanks and best regards,
Wenjie

Sep 16 '06 #1
7 2584

go****@yahoo.co m 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 "Programmin g Pearls" and not "Introducti on
to Obfuscation?" 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.)

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

--
Bill Pursell

Sep 16 '06 #2
"Bill Pursell" <bi**********@g mail.comwrites:
go****@yahoo.co m 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 "Programmin g Pearls" and not "Introducti on
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
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).

Yours,

--
Jean-Marc
Sep 16 '06 #3
Jean-Marc Bourguet wrote:
"Bill Pursell" <bi**********@g mail.comwrites:
go****@yahoo.co m 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 "Programmin g Pearls" and not "Introducti on
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

Sep 17 '06 #4
go****@yahoo.co m 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
your hint?
>From N869:
6.5.7 Bitwise shift operators

Syntax

[#1]
shift-expr:
additive-expr
shift-expr << additive-expr
shift-expr >additive-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

Sep 17 '06 #5
go****@yahoo.co m 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
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?
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
Sep 17 '06 #6
CBFalconer <cb********@yah oo.comwrites:
>>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.
Sep 17 '06 #7
Jean-Marc Bourguet wrote:
go****@yahoo.co m 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 -- tm*@nj.net -- AB2SB

Sep 17 '06 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

10
7072
by: Stefan Höhne | last post by:
Hi, as I recon, std::vector::clear()'s semantics changed from MS VC++ 6.0 to MS' DOT.NET - compiler. In the 6.0 version the capacity() of the vector did not change with the call to clear(), in DOT.NET the capacity() is reduced to 0.
16
2729
by: Kitty | last post by:
Hi, everyone. Given a vector<int>, what is the fastest way to find out whether there is a repeated element in it? The result is just "true" or "false". Thanks. Kitty
28
1946
by: VK | last post by:
A while ago I wrote a "Vector data type" script using DOM interface to select.options. That was a (beautiful) mind game :-) rather than a practical thing to use. Here is another attempt open for criticism, this time dead serious. I really need an effective Vector emulator for a project (as much effective as something not implemeted in language but emulated by means of the language itself is: a
16
2401
by: call_me_anything | last post by:
why is the following not allowed : vector <Base *vec_of_base; vector <Derived *vec_of_derived; vec_of_base = vec_of_derived; Note : The following is allowed :
2
3320
by: danielhdez14142 | last post by:
Some time ago, I had a segment of code like vector<vector<int example; f(example); and inside f, I defined vector<int>'s and used push_back to get them inside example. I got a segmentation fault which I resolved by doing vector<vector<int example; example.push_back(vector<int>());
32
4017
by: T. Crane | last post by:
Hi, I'm struggling with how to initialize a vector<vector<double>> object. I'm pulling data out of a file and storing it in the vector<vector<double>object. Because any given file will have a large amount of data, that I read off using an ifstream object, I don't want to use the push_back method because this grows the vector<vector<double>dynamically, and that will kill my execution time. So, I want to reserve space first, using, of...
18
2503
by: subramanian100in | last post by:
Consider a class that has vector< pair<int, string>* c; as member data object. I need to use operator>to store values into this container object and operator<< to print the contents of the container. I have written both these operators as non-friend functions.
1
2289
by: pitjpz | last post by:
We have moved our Database to another server. The server it was on used SQL 4 and the new one its on now uses SQL5 the only problem we can find is that when you attempt to delete a record from the DB the following happens: When Deleting a record: Fatal Error: Can't call method "fetchrow_arrayref" on an undefined value at GT::SQL::File::delete_records line 275. Stack Trace: GT::Base (2704): main::fatal called at...
6
7377
by: Mr. K.V.B.L. | last post by:
I want to start a map with keys but an empty vector<string>. Not sure what the syntax is here. Something like: map<string, vector<string MapVector; MapVector.insert(make_pair("string1", new vector<string>)); MapVector.insert(make_pair("string2", new vector<string>)); MapVector.insert(make_pair("string3", new vector<string>));
0
9227
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
9143
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9077
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
8019
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
4497
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4761
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
3202
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2588
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2137
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.