By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,898 Members | 2,006 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,898 IT Pros & Developers. It's quick & easy.

Strange Bit Shift Operator

P: n/a
vj
Hello group,

I am working on a compression tool and saw this puzzling bit shit
behaviour on a VC++6.0 compiler.

#include <iostream>
using namespace std;
typedef unsigned char uchar;
#define NBITS(x) ((uchar)(~0u<<sizeof(0u)*8-(x) >>sizeof(0u)*8-(x)))
// NBITS forms a byte containing specified number of bits turned on.
void main()
{ int k=0;
cout<<hex<<(int) NBITS(k)<<endl;
cout<<hex<<(int) NBITS(0)<<endl;
}
/****output***/
ff
00
/****output ends***/

intrestingly i am getting two diffrent values for the same input. I
really dont know whats causing it, but i have a huntch that the
Preprocessor is calculating(for the constant value 0) the values
diffrent way then the code that generated by the compiler ( which is
used at the run time).

Thanks in advance,

----
VJ

Dec 13 '05 #1
Share this Question
Share on Google+
11 Replies


P: n/a

vj wrote:
Hello group,

I am working on a compression tool and saw this puzzling bit shit
behaviour on a VC++6.0 compiler.

#include <iostream>
using namespace std;
typedef unsigned char uchar;
#define NBITS(x) ((uchar)(~0u<<sizeof(0u)*8-(x) >>sizeof(0u)*8-(x)))
// NBITS forms a byte containing specified number of bits turned on.
void main()
{ int k=0;
cout<<hex<<(int) NBITS(k)<<endl;
cout<<hex<<(int) NBITS(0)<<endl;
}
/****output***/
ff
00
/****output ends***/


I would eliminate the macro, it's a mess. Just use an array:

const unsigned char nBits[] =
{ 0x00, 0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF };

and replace NBITS(k) with nBits[k].

Greg

Dec 13 '05 #2

P: n/a
vj wrote:
Hello group, #include <iostream>
using namespace std;
typedef unsigned char uchar;
#define NBITS(x) ((uchar)(~0u<<sizeof(0u)*8-(x) >>sizeof(0u)*8-(x)))
// NBITS forms a byte containing specified number of bits turned on.
void main()
{ int k=0;
cout<<hex<<(int) NBITS(k)<<endl;
cout<<hex<<(int) NBITS(0)<<endl;
}
/****output***/
ff
00
/****output ends***/

intrestingly i am getting two diffrent values for the same input. I
really dont know whats causing it, but i have a huntch that the
Preprocessor is calculating(for the constant value 0) the values
diffrent way then the code that generated by the compiler ( which is
used at the run time).


5.8p1 : About shift operators :
The behavior is undefined if the right operand is negative, or greater
than or equal to the length in bits of the promoted left operand.

Here, since sizeof(0u) * 8 = number of bits in ~0u, it is "undefined
behaviour". In other words, anything may happen and no diagnosis is
necessary.

Dec 13 '05 #3

P: n/a
vj wrote:
I am working on a compression tool and saw this puzzling bit shit
behaviour on a VC++6.0 compiler.
It's the same in VC++ v7.1, and probably many other compilers.
#include <iostream>
using namespace std;
typedef unsigned char uchar;
#define NBITS(x) ((uchar)(~0u<<sizeof(0u)*8-(x) >>sizeof(0u)*8-(x)))
This macro assumes that a byte is 8 bits. Dangerous.
// NBITS forms a byte containing specified number of bits turned on.
void main()
int main()
{ int k=0;
cout<<hex<<(int) NBITS(k)<<endl;
cout<<hex<<(int) NBITS(0)<<endl;
}
/****output***/
ff
00
I get a single 0. How do you get two zeros?
/****output ends***/

intrestingly i am getting two diffrent values for the same input. I
really dont know whats causing it, but i have a huntch that the
Preprocessor is calculating(for the constant value 0) the values
diffrent way then the code that generated by the compiler ( which is
used at the run time).


Yes. For a constant 0 the result is calculated in compile-time, and it is
"correct". The "incorrect" result is calculated during run-time, and it
involves shifting of "all bits set" value to the left 32 times, which is
the same as not shifting it at all. The expression 'sizeof(0u)*8 - k'
yields 32, then the left shift of (32 % 32) is applied.

Here is a fixed macro:

#define NBITS(x) ((unsigned char)~(~0u << (x % 8)))

Besides doing the right thing it evaluates 'x' only once, which is often
important.

V
Dec 13 '05 #4

P: n/a

Victor Bazarov wrote:
Yes. For a constant 0 the result is calculated in compile-time, and it is
"correct". The "incorrect" result is calculated during run-time, and it
involves shifting of "all bits set" value to the left 32 times, which is
the same as not shifting it at all. The expression 'sizeof(0u)*8 - k'
yields 32, then the left shift of (32 % 32) is applied.


What do you exactly mean by "left shift by 32 is same as not shifting
it at all"?
And from where does 32%32 come up here?

Dec 13 '05 #5

P: n/a
Victor Bazarov <v.********@comacast.net> wrote:
vj wrote:
I am working on a compression tool and saw this puzzling bit shit
behaviour on a VC++6.0 compiler.


It's the same in VC++ v7.1, and probably many other compilers.


Interesting, the following program (which should be the same as the
OP's) outputs

0
0

for me using VC++ v7.1:
#include <iostream>
#include <iomanip>

typedef unsigned char uchar;

#define NBITS(x) ((uchar) (~0u << sizeof(0u) * 8 - (x) >> sizeof(0u) * 8 - (x)))

int main()
{
int k = 0;
std::cout << std::hex << (int) NBITS(k) << '\n';
std::cout << std::hex << (int) NBITS(0) << '\n';

return 0;
}

--
Marcus Kwok
Dec 13 '05 #6

P: n/a
Neelesh Bodas wrote:
Victor Bazarov wrote:
Yes. For a constant 0 the result is calculated in compile-time, and it is
"correct". The "incorrect" result is calculated during run-time, and it
involves shifting of "all bits set" value to the left 32 times, which is
the same as not shifting it at all. The expression 'sizeof(0u)*8 - k'
yields 32, then the left shift of (32 % 32) is applied.

What do you exactly mean by "left shift by 32 is same as not shifting
it at all"?


I peeked at the assembly code, and knowing the CPU instructions made this
statement, which is very platform-specific. I apologise.
And from where does 32%32 come up here?


From the same source.

V
Dec 13 '05 #7

P: n/a
Marcus Kwok wrote:
Victor Bazarov <v.********@comacast.net> wrote:
vj wrote:
I am working on a compression tool and saw this puzzling bit shit
behaviour on a VC++6.0 compiler.


It's the same in VC++ v7.1, and probably many other compilers.

Interesting, the following program (which should be the same as the
OP's) outputs

0
0

for me using VC++ v7.1:
#include <iostream>
#include <iomanip>

typedef unsigned char uchar;

#define NBITS(x) ((uchar) (~0u << sizeof(0u) * 8 - (x) >> sizeof(0u) * 8 - (x)))

int main()
{
int k = 0;
std::cout << std::hex << (int) NBITS(k) << '\n';
std::cout << std::hex << (int) NBITS(0) << '\n';

return 0;
}


Yep.

<compiler-specific>
Curiously enough, the behaviour of the Release build differs from the
Debug build. It must have something to do with the optimization...
</compiler-specific>

V
Dec 13 '05 #8

P: n/a
On 13 Dec 2005 09:23:34 -0800 in comp.lang.c++, "Greg"
<gr****@pacbell.net> wrote,
vj wrote:
#define NBITS(x) ((uchar)(~0u<<sizeof(0u)*8-(x) >>sizeof(0u)*8-(x)))
I would eliminate the macro, it's a mess. Just use an array:


But that blows the whole point; it prevents the compiler from
evaluating it as a constant expression at compile time!

However, I agree the given #define is horrible. I propose:
#define NBITS(x) (~(~0u << (x)))

Dec 13 '05 #9

P: n/a
vj wrote:
I am working on a compression tool and saw this puzzling bit shit
behaviour on a VC++6.0 compiler.
Accurate use of adjectives !
typedef unsigned char uchar;
#define NBITS(x) ((uchar)(~0u<<sizeof(0u)*8-(x) >>sizeof(0u)*8-(x)))
This causes undefined behaviour when x is 0 (the number of bits
in a bit shift must be less than the number of bits in the thing
being shifted).

I don't know why anyone would prefer this to:
#define NBITS(x) ( (1u << (x)) - 1 )

which works on the range 0 <= x <= 31 (assuming 32-bit int).
void main()
Should be:
int main()
{ int k=0;
cout<<hex<<(int) NBITS(k)<<endl;
cout<<hex<<(int) NBITS(0)<<endl;
}
/****output***/
ff
00
/****output ends***/


No surprise.

Dec 13 '05 #10

P: n/a
vj
Hello Friends,

Thank you all for your wonderful as well as enlighting suggestion the
original macro definition was really a big big mess ( was really a
quick fix solution) i have finally converted it to
#define NBITS(x) (~(~0u << (x))) //thanks david

But still i suppose that the problem remains the same as to what is
wrong with this macro definition
#define NBITS(x) ( (uchar) (~0u << sizeof(0u) * 8 - (x) >>
sizeof(0u)*8-(x) ) )

Assumptions here were that x<=8 (it will never be greater than 8)
hence the expression sizeof(0u)*8-(x) >=0 (never negative). So that
answers the question
of undefined behaviour due to negative values.

I went through the generated assemble code and i too believe that the
culprit is the SHL instruction.
take look at the generated code for
/******code*******/
unsigned i,j,k=0;
9: i= ~0u<< sizeof(0u)*8+k;
mov ecx,dword ptr [ebp-0Ch]
add ecx,20h
or eax,0FFFFFFFFh
shl eax,cl ///the culprit
mov dword ptr [ebp-4],eax
/***code ends****/

it seems that if shl is given a shift count >=32 then it simpliy takes
it mod with 32 ( count %32) as Victor said and then shifts it. I tried
to search the net for info on this issue with SHL but could not find
any thing.
I does seems that it is a well known issue as it is evident from
compiler output for constant expressions but some how its overlooked
when generating runtime code.
I am now planning to post it on usenet group for more clarification.

Once again thanks you all,

----
vj

Dec 14 '05 #11

P: n/a
vj
Hello once again,

I did a post on comp.lang.asm.x86 group regarding the problem and their
reply have confirmed Victor and My suspicion that some where the
ShiftCount%32 is happening. The group has said that the SHL instruction
takes only takes 5 LSBs and maskes of the rest. That means that a
shift count of 0x20 will be masked of with 0x1F = 0x00 . Thus no bit
shift actually takes place.

I hope that winds up the topic and clear every thing.

Thanks for the support,
----
VJ

Dec 15 '05 #12

This discussion thread is closed

Replies have been disabled for this discussion.