Right shift >> weird result... Why?

[Mick_fae_Glesga]

OK, the solution to this is probably blindingly obvious to everyone,
but... surely it can't be right.

I am compiling with borland bcc32 free compiler

this piece of code is designed to identify the most significant bit in
a given element in an array of unsigned longs. Now I realise there may
be a more efficient way to do this, and if you know a better way please
let me know.

However, the efficieny of the code is neither here nor there, the
point is the weird result:

// an array of two unsigned longs
unsigned long twoULongs[2];

// initial amount to shift by
unsigned long rShift = 0;

// fill the lowest element of the array with its maximum
// possible value
twoULongs[0] = 0xFFFFFFFF;
twoULongs[1] = 0;

// this loop should end when we have discovered the most significant
bit in
// element 0 of the array storing the bit number in
rShift
// (actually, the bit position + 1)
while((twoULongs[0] >> rShift) != 0)
{
// Display the value of the shift (for debug purposes)
cout << (twoULongs[0] >> rShift) << endl;
// since we haven't found the msb yet, shift by one more next time
rShift++;
// pause the program so we can see whats going on for debug
// purposes
cin.get();
}

Now the output, as twoULongs[0] tends towards 0 is:

31, 15, 7, 3, 1, 4294967295 !!!

Whoa!! we just ticked over back to the highest possible unsigned
long!!!

So why didn't it hit 0 after 1?

please rate my idiocy, and if you know whats wrong, tell me

 

[Victor Bazarov]

OK, the solution to this is probably blindingly obvious to everyone,
but... surely it can't be right.

I am compiling with borland bcc32 free compiler

this piece of code is designed to identify the most significant bit in
a given element in an array of unsigned longs. Now I realise there
may be a more efficient way to do this, and if you know a better way
please let me know.

However, the efficieny of the code is neither here nor there, the
point is the weird result:

// an array of two unsigned longs
unsigned long twoULongs[2];

// initial amount to shift by
unsigned long rShift = 0;

// fill the lowest element of the array with its maximum
// possible value
twoULongs[0] = 0xFFFFFFFF;
twoULongs[1] = 0;

// this loop should end when we have discovered the most significant
bit in
// element 0 of the array storing the bit number in
rShift
// (actually, the bit position + 1)
while((twoULongs[0] >> rShift) != 0)
{
// Display the value of the shift (for debug purposes)
cout << (twoULongs[0] >> rShift) << endl;
// since we haven't found the msb yet, shift by one more next time
rShift++;
// pause the program so we can see whats going on for debug
// purposes
cin.get();
}

Now the output, as twoULongs[0] tends towards 0 is:

31, 15, 7, 3, 1, 4294967295 !!!

Whoa!! we just ticked over back to the highest possible unsigned
long!!!

So why didn't it hit 0 after 1?

please rate my idiocy, and if you know whats wrong, tell me

Shifting with the number larger or the same than the number of bits
in the left operand causes undefined behaviour. On Intel processors,
IIRC, shifting instruction only uses the lower 6 bits, but C++ cannot
define shifting in those terms, so it doesn't define it at all.

So, as soon as rShift reaches 32, you get no shift at all. Or you
can get a nasty email. Or the demons can fly out of your nose.


V

 

[Mick_fae_Glesga]

Ah, OK, thanks... I was hoping it would be zero....

Well, do you know of any other way of asking 'What is the highest set
bit in this number?' does such a command exist? or do I have to look
at each bit individually?

 

[Jack Saalweachter]

OK, the solution to this is probably blindingly obvious to everyone,
but... surely it can't be right.

I am compiling with borland bcc32 free compiler

this piece of code is designed to identify the most significant bit in
a given element in an array of unsigned longs. Now I realise there may
be a more efficient way to do this, and if you know a better way please
let me know.

However, the efficieny of the code is neither here nor there, the
point is the weird result:

// an array of two unsigned longs
unsigned long twoULongs[2];

// initial amount to shift by
unsigned long rShift = 0;

// fill the lowest element of the array with its maximum
// possible value
twoULongs[0] = 0xFFFFFFFF;
twoULongs[1] = 0;

// this loop should end when we have discovered the most significant
bit in
// element 0 of the array storing the bit number in
rShift
// (actually, the bit position + 1)
while((twoULongs[0] >> rShift) != 0)
{
// Display the value of the shift (for debug purposes)
cout << (twoULongs[0] >> rShift) << endl;
// since we haven't found the msb yet, shift by one more next time
rShift++;
// pause the program so we can see whats going on for debug
// purposes
cin.get();
}

Now the output, as twoULongs[0] tends towards 0 is:

31, 15, 7, 3, 1, 4294967295 !!!

Whoa!! we just ticked over back to the highest possible unsigned
long!!!

So why didn't it hit 0 after 1?

please rate my idiocy, and if you know whats wrong, tell me

The problem is that the result of op >> is undefined when the value on
the right is greater than or equal to the number of bits on the left.
Or as the Standard (5.8.1) puts it:

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

"Undefined behavior" is the worst kind, because we literally don't know
what happens in that case. The program could end, your hard-drive could
be deleted, the program is quite literally free to do whatever you want.

WE WOULD LIKE to be able to say, "Oh, your compiler is obviously doing
'a >> (b % 32)'," but unless your compiler specifically tells you this,
we have no reason to think so. Even if it did say so, you probably
shouldn't rely on it, because if you switch compilers, your code could
stop working.

What you have to do is ask yourself, "What do I want to happen in this
situation?", and then write your code to explicitly do this. For
instance, if you want your code to produce zeros when you right-shift by
too many places, your must explicitly say:

unsigned long v = 0;

if (rShift >= numberOfBitsInAnUL)
v = 0;
else
v = twoULongs[0] >> rShift;

// work with v instead of twoULongs[0] >> rShift.


Simply put, any other course of action is madness.


Jack Saalweachter

 

[Kai-Uwe Bux]

Ah, OK, thanks... I was hoping it would be zero....

Well, do you know of any other way of asking 'What is the highest set
bit in this number?' does such a command exist? or do I have to look
at each bit individually?

What about:

template < typename Unsigned >
Unsigned highest_bit ( Unsigned u ) {
Unsigned result = 0;
while ( u != 0 ) {
++result;
u >>= 1;
}
return ( result );
}

#include <iostream>

int main ( void ) {
unsigned long u;
while ( std::cin >> u ) {
std::cout << u << " --> " << highest_bit(u) << '\n';
}
}


Best

Kai-Uwe Bux

 

[Tomás]

Mick_fae_Glesga posted:

this piece of code is designed to identify the most significant bit in
a given element in an array of unsigned longs.

Well first, I'd take zero:

0000 0000

Then flip all the bits:

1111 1111

Then shift once to the right:

0111 1111

Then flip the bits:

1000 0000


Now we have the highest bit. Let's take a sample value to determine its
highest bit which is set:

0010 1100

We'll bitwise AND it with our high bit. If the result is true, then that
bit was set... otherwise, we shift our high bit to the right, yielding:

0100 0000

And then try another bitwise AND.

Here comes some unchecked, off-the-cuff code. (It's not spectacular, but
it's the best I can produce in fifteen minutes

/* The following class provides a "universal" way
for default initialising an object (regardless of
whether it's a primitive type, a POD struct or
union, or a Fancy Class Type, or an array) */

template<class T>
class DefaultInitBearer {
private:

T object;

public:

DefaultInitBearer() : object() {}

T& GetRef() { return object; }

const T& GetRef() const { return object; }

};


/* The following function will convert from
index from the left to index from the right,
and vice versa.

For example, if we're dealing with a 16-Bit
unsigned variable, then:

0 == 15, 1 == 14, 2 == 13, 3 == 12, 4 == 11
*/

template<class T>
unsigned InvertBitIndex(unsigned const index)
{
DefaultInitBearer<T> ander_bearer;
T &ander = ander_bearer.GetRef();

ander = ~ander;

unsigned max_index = 0;

while ( ander >>= T(1) ) ++max_index;

return max_index - index;
}

#include <limits>

template<class T>
unsigned MostSignificantBitWhichIsOn( const T& obj )
{
/* First let's get an object and make it zero */

DefaultInitBearer<T> ander_bearer;
T &ander = ander_bearer.GetRef();


/* Now let's flip its bits */

ander = ~ander;


/* Now let's shift it to the right once */

ander >>= T(1);


/* Now let's flip it again */

ander = ~ander;


/* Now let's run a loop to find the highest bit */

for ( unsigned index = 0; ; ++index )
{
if ( obj & ander ) return InvertBitIndex<T>(index);

ander >>= T(1);

if (!ander) return std::numeric_limits<unsigned>::max();
}
}

#include <iostream>
using std::cout;

#include <cstdlib>

int main()
{
cout << MostSignificantBitWhichIsOn(0U) << '\n';
cout << MostSignificantBitWhichIsOn(1U) << '\n';
cout << MostSignificantBitWhichIsOn(2U) << '\n';
cout << MostSignificantBitWhichIsOn(3U) << '\n';
cout << MostSignificantBitWhichIsOn(4U) << '\n';
cout << MostSignificantBitWhichIsOn(5U) << '\n';
cout << MostSignificantBitWhichIsOn(6U) << '\n';

cout << MostSignificantBitWhichIsOn(60U) << '\n';
cout << MostSignificantBitWhichIsOn(61U) << '\n';
cout << MostSignificantBitWhichIsOn(62U) << '\n';
cout << MostSignificantBitWhichIsOn(63U) << '\n';
cout << MostSignificantBitWhichIsOn(64U) << '\n';
cout << MostSignificantBitWhichIsOn(65U) << '\n';

std::system("PAUSE");
}


-Tomás

 

[Victor Bazarov]

What about:

template < typename Unsigned >
Unsigned highest_bit ( Unsigned u ) {
Unsigned result = 0;
while ( u != 0 ) {
++result;
u >>= 1;
}
return ( result );
}

#include <iostream>

int main ( void ) {
unsigned long u;
while ( std::cin >> u ) {
std::cout << u << " --> " << highest_bit(u) << '\n';
}
}


Best

Kai-Uwe Bux

Or

unsigned highest_bit(unsigned a) {
return log(a) / log(2);
}

V

 

[Kai-Uwe Bux]

Or

unsigned highest_bit(unsigned a) {
return log(a) / log(2);
}

Hm, I just don't trust floating point operations:


template < typename Unsigned >
Unsigned highest_bit_kub ( Unsigned u ) {
Unsigned result = 0;
while ( u != 0 ) {
++result;
u >>= 1;
}
return ( result );
}

#include <cmath>

template < typename Unsigned >
Unsigned highest_bit_vb ( Unsigned u ) {
return std::log(u) / std::log(2);
}

#include <iostream>
#include <iomanip>

int main ( void ) {
unsigned long u;
for ( u = 0; u < 25; ++u ) {
std::cout << std::setw(3) << u
<< " highest_bit_kub: " << highest_bit_kub(u)
<< ", highest_bit_vb: " << highest_bit_vb(u) << '\n';
}
}


Output on my machine:

0 highest_bit_kub: 0, highest_bit_vb: 0
1 highest_bit_kub: 1, highest_bit_vb: 0
2 highest_bit_kub: 2, highest_bit_vb: 1
3 highest_bit_kub: 2, highest_bit_vb: 1
4 highest_bit_kub: 3, highest_bit_vb: 2
5 highest_bit_kub: 3, highest_bit_vb: 2
6 highest_bit_kub: 3, highest_bit_vb: 2
7 highest_bit_kub: 3, highest_bit_vb: 2
8 highest_bit_kub: 4, highest_bit_vb: 2
9 highest_bit_kub: 4, highest_bit_vb: 3
10 highest_bit_kub: 4, highest_bit_vb: 3
11 highest_bit_kub: 4, highest_bit_vb: 3
12 highest_bit_kub: 4, highest_bit_vb: 3
13 highest_bit_kub: 4, highest_bit_vb: 3
14 highest_bit_kub: 4, highest_bit_vb: 3
15 highest_bit_kub: 4, highest_bit_vb: 3
16 highest_bit_kub: 5, highest_bit_vb: 4
17 highest_bit_kub: 5, highest_bit_vb: 4
18 highest_bit_kub: 5, highest_bit_vb: 4
19 highest_bit_kub: 5, highest_bit_vb: 4
20 highest_bit_kub: 5, highest_bit_vb: 4
21 highest_bit_kub: 5, highest_bit_vb: 4
22 highest_bit_kub: 5, highest_bit_vb: 4
23 highest_bit_kub: 5, highest_bit_vb: 4
24 highest_bit_kub: 5, highest_bit_vb: 4


Note in particular the lines 7,8,9 as opposed to 3,4 and 15,16.


Best

Kai-Uwe Bux

 

[Jerry Coffin]

@i39g2000cwa.googlegroups.com>, (e-mail address removed)
says...

Ah, OK, thanks... I was hoping it would be zero....

Well, do you know of any other way of asking 'What is the highest set
bit in this number?' does such a command exist? or do I have to look
at each bit individually?

The easy and obvious way is to count the number of right
shifts until the number turns into zero (be sure when you
do the right-shift that it's unsigned, or this may not
work at all though).

At least theoretically, it should be faster to use
bisection to find the top bit that's set. Here's some
code to work with an 8-bit number:

int top_set_bit(char x) {
// Since we're looking for the top bit that's set, we
// always start with the upper bits, and look at the
// lower bits only if none of the upper bits was set.
//
// assumes 8-bit char.
//
// returns number (0-7) of bit that was set,
// or -1 if no bit was set.
//

if (x & 0xf0)
if (x & 0xc0)
if (x & 0x80)
return 7;
else
return 6;
else if (x & 0x20)
return 5;
else
return 4;
else
if (x & 0x0c)
if (0x08)
return 3;
else
return 2;
else if (x & 2)
return 1;
else if (x & 1)
return 0;
return -1;
};

Extending this to larger sizes is left as an exercise for
the reader (as is figuring out the number of bits in an
int, or whatever type you care about). I'd consider
having a function to figure out which byte in an int was
set, and then use the code above to find the correct bit
in that byte.

 

[Zara]

OK, the solution to this is probably blindingly obvious to everyone,
but... surely it can't be right.

I am compiling with borland bcc32 free compiler

this piece of code is designed to identify the most significant bit in
a given element in an array of unsigned longs. Now I realise there may
be a more efficient way to do this, and if you know a better way please
let me know.

<...>

// 32 bit unsigned int case

int highest_bit(unsigned int value) {
unsigned int highest_one_set = value & ~( value >> 1 ) ) ;
if (highest_one_set==0) {
return -1;
}
int result=1;
if ( (highest_one_set & 0x0000ffff) == 0 ) {
result+=16;
highest_one_set>>=16;
}
if ( (highest_one_set & 0x000000ff) == 0 ) {
result+=8;
highest_one_set>>=8;
}
if ( (highest_one_set & 0x0000000f) == 0 ) {
result+=4;
highest_one_set>>=4;
}
if ( (highest_one_set & 0x00000003) == 0 ) {
result+=3;
highest_one_set>>=>;
}
return result - (highest_one_set&1);
}

 

[Zara]

<...>

// 32 bit unsigned int case

int highest_bit(unsigned int value) {

unsigned int highest_one_set = value & ~( value >> 1 ) ) ;

oops! this one is wrong! So the rest is wrong, too

if (highest_one_set==0) {
return -1;
}
int result=1;
if ( (highest_one_set & 0x0000ffff) == 0 ) {
result+=16;
highest_one_set>>=16;
}
if ( (highest_one_set & 0x000000ff) == 0 ) {
result+=8;
highest_one_set>>=8;
}
if ( (highest_one_set & 0x0000000f) == 0 ) {
result+=4;
highest_one_set>>=4;
}
if ( (highest_one_set & 0x00000003) == 0 ) {
result+=3;
highest_one_set>>=>;
}
return result - (highest_one_set&1);
}

Rewritten, with more thinking...

int highest_bit(unsigned int value) {

if (value==0) {
return -1;
}
int result=0;
if ( value & 0xffff0000) != 0 ) {
result+=16;
value>>=16;
}
if ( value & 0x0000ff00) != 0 ) {
result+=8;
value>>=8;
}
if ( value & 0x000000f0) != 0 ) {
result+=4;
value>>=4;
}
if ( (value& 0x0000000c0) != 0 ) {
result+=2;
value>>=2;
}
if ( (value& 0x000000002) != 0 ) {
result+=1;
}
return result;
}


I think that one is right. But I am not very good at thinking ;-)

Zara

 

[CAFxX]

Mick_fae_Glesga ha scritto:

Ah, OK, thanks... I was hoping it would be zero....

Well, do you know of any other way of asking 'What is the highest set
bit in this number?' does such a command exist? or do I have to look
at each bit individually?

look at your compiler intrinsics definitions. you should find it there
(at least gcc, msvc and icc have an intrinsic doing that)

 

[persenaama]

Well, do you know of any other way of asking 'What is the highest set

bit in this number?' does such a command exist?

typedef unsigned int uint32; // platform specific - comes from a
configuration system, OFF TOPIC on clc++!

inline int msb(uint32 v)
{
int base = 0;
uint32 n = v & 0xffff0000; if ( n ) { base |= 16; v = n; }
n = v & 0xff00ff00; if ( n ) { base |= 8; v = n; }
n = v & 0xf0f0f0f0; if ( n ) { base |= 4; v = n; }
n = v & 0xcccccccc; if ( n ) { base |= 2; v = n; }
return v & 0xaaaaaaaa ? base | 1 : base;
}