Strange Bit Shift Operator

[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,

 

[Greg]

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

 

[Victor Bazarov]

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

 

[Neelesh Bodas]

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.

 

[Neelesh Bodas]

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?

 

[Marcus Kwok]

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;
}

 

[Victor Bazarov]

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

 

[Victor Bazarov]

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

 

[David Harmon]

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

[/QUOTE]

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

 

[Old Wolf]

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.

 

[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]

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,