When does this function exit

shaiko · May 26, 2015

Hello,

Taken from a programming book - this function is supposed to receive a 32 bit number and return the position of the 3rd bit that's a binary '1'.

Code:

int FindThird1(int reg)
{
int count = 0;
for (int i=0; i<32; i++)
{
count += (reg>>i)&1;
if (count == 3)
return i;
}
return -1;
}

A few questions:

1. The condition for exiting the for loop is i=32. On the other hand we have the return value statement:
if (count == 3)
return i;
So...when will the function exit? Will it loop over all 32 bits or will the
condition marked in red override this and cause the function to exit as soon as it's met?

2. What is the purpose of the "return -1" line ?

milan.rajik · May 26, 2015

Why don't you debug and see what happens ?

horace1 · May 26, 2015

looks to me a though it will exit when it finds the third non zero bit in a word, e.g. 0x1010101 will return 16
it returns -1 if there is not a third non zero bit in a word, i.e. it exits the for() loop

shaiko · May 26, 2015

Thanks horace1,

So you're saying that the "return" statement overrides the loop condition?

xenos · May 26, 2015

It not so simple folks.
Althow locating the 3rd non zero bit (starting from LSB), seems as the intended behavior, it may not work as excpected.

The variable is of type signed int.
If you bit shift a negative value, you may not get the required results.
You may reed this article:
http://stackoverflow.com/questions/1857928/right-shifting-negative-numbers-in-c
and this C draft document:
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1336.pdf (page 99)

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 / 2E2. If E1 has a signed type and a negative value, the
resulting value is implementation-defined.

Just an example

Code:

void _showbin(unsigned int x){
	printf("%08x ",x);
	for(unsigned i=8*sizeof(x),n=0;i--;){
		putchar(((x >> i)&1) ? '1' : '0');
		if(++n == 4){
			n = 0;
			putchar('.');
		}
	}
	putchar('\t');
}

void showbin(int x){
	_showbin(*((unsigned int *)&x));
}

#define Showbin(a)	{ showbin(a); printf("%s\n", #a); }

int main(void){
	Showbin(1);
	Showbin(1>>5);
	Showbin(1<<5);

	showbin((-1));
	Showbin((-1)>>5);

	Showbin(-2);
	Showbin((-2)>>5);
	Showbin((-2)<<5);
	return 0;
}

Results in:

Code:

00000001 0000.0000.0000.0000.0000.0000.0000.0001.	1
00000000 0000.0000.0000.0000.0000.0000.0000.0000.	1>>5
00000020 0000.0000.0000.0000.0000.0000.0010.0000.	1<<5
ffffffff 1111.1111.1111.1111.1111.1111.1111.1111.	
ffffffff 1111.1111.1111.1111.1111.1111.1111.1111.	(-1)>>5
fffffffe 1111.1111.1111.1111.1111.1111.1111.1110.	-2
ffffffff 1111.1111.1111.1111.1111.1111.1111.1111.	(-2)>>5
ffffffc0 1111.1111.1111.1111.1111.1111.1100.0000.	(-2)<<5

So when it shifts the bits to determine if are set or not, the result may be tricky.
It is a bad programming behavior to shift signed numbers.

Tahmid · May 27, 2015

The loop body is executed every iteration. But when a return statement is called or executed, the function returns, thus exiting.

zorro · May 27, 2015

shaiko said:
1. The condition for exiting the for loop is i=32. On the other hand we have the return value statement:
if (count == 3)
return i;
So...when will the function exit? Will it loop over all 32 bits or will the
condition marked in red override this and cause the function to exit as soon as it's met?

The function exits as soon as the red condition is met.
If the word has less than three '1's, then that condition is not met and the 'for' loops over all 32 bits and ends.

2. What is the purpose of the "return -1" line ?

The funcion returns -1 if the word has less than three '1's.

xenos said:
If you bit shift a negative value, you may not get the required results.

This can not happen in the code of post #1.

Z

horace1 · May 27, 2015

shaiko said:
Thanks horace1,

So you're saying that the "return" statement overrides the loop condition?

yes it exits the function
the break statement can also terminate a for, do or while statement

shaiko · May 27, 2015

xenos,

It is a bad programming behavior to shift signed numbers

Can you suggest something that will work for signed numbers?

Tahmid · May 27, 2015

If you shift, you want to perform an arithmetic shift that preserves the sign (sign extension). You can bit mask the number after shifting it, and then use this result from there on.

shaiko · May 27, 2015

Can you post a code example please?

xenos · May 27, 2015

shaiko said:
xenos,

Can you suggest something that will work for signed numbers?

It depends. What would you excpect by shifting a negative number?

Shifting is usable in bit operations on unsigned numbers.
You can replace "int reg;" with "unsigned reg;"

horace1 · May 27, 2015

the C standard does not specify if >> performs logical or arithmetic shift
if arithmetic it will sign extend a negative value, if logical it shifts in a 0

I remember a collegue spending days debugging software he was porting to a new machine where >> was different from the original imolementation system

FvM · May 27, 2015

Can you suggest something that will work for signed numbers?

It should be noted that the intended behaviour of the code in post #1 is unclear by itself, no only by the implementation depend behaviour of >> with signed numbers. So you must tell first which result you want for signed numbers. Are you considering the "one" bits of two's complement signed number representation?

zorro · May 28, 2015

The behaviour of the code in post #1 is not dependent of the behaviour (arithmetic or logical) of the ">>" operator, provided that the type has 32 bits.
It does not matter even if the type is signed or unsigned int, again provided that is has 32 bits.

Z

FvM · May 28, 2015

The behaviour of the code in post #1 is not dependent of the behaviour (arithmetic or logical) of the ">>" operator, provided that the type has 32 bits.

Yes, because none of the shifted-in bits gets the chance to be counted. Thanks for reminding the obvious.

When does this function exit

Advanced Member level 5

Banned

Advanced Member level 5

Advanced Member level 5

Full Member level 4

Advanced Member level 6

Advanced Member level 4

Advanced Member level 5

Advanced Member level 5

Advanced Member level 6

Advanced Member level 5

Full Member level 4

Advanced Member level 5

Super Moderator

Advanced Member level 4

Super Moderator

Similar threads

Privacy & Transparency

Privacy & Transparency