Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

When does this function exit

Status
Not open for further replies.

shaiko

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,644
Helped
303
Reputation
608
Reaction score
297
Trophy points
1,363
Activity points
18,300
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 ?
 

horace1

Advanced Member level 5
Joined
Nov 18, 2008
Messages
2,123
Helped
596
Reputation
1,188
Reaction score
573
Trophy points
1,393
Location
Norwich, UK
Activity points
13,069
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
 
  • Like
Reactions: shaiko

    shaiko

    Points: 2
    Helpful Answer Positive Rating

shaiko

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,644
Helped
303
Reputation
608
Reaction score
297
Trophy points
1,363
Activity points
18,300
Thanks horace1,

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

xenos

Full Member level 4
Joined
May 9, 2015
Messages
212
Helped
82
Reputation
164
Reaction score
81
Trophy points
28
Location
127.0.0.1
Activity points
1,182
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:
https://stackoverflow.com/questions/1857928/right-shifting-negative-numbers-in-c
and this C draft document:
https://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.
 
Last edited:
  • Like
Reactions: shaiko

    shaiko

    Points: 2
    Helpful Answer Positive Rating

zorro

Advanced Member level 4
Joined
Sep 6, 2001
Messages
1,131
Helped
357
Reputation
712
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,907
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.

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
 
  • Like
Reactions: shaiko

    shaiko

    Points: 2
    Helpful Answer Positive Rating

horace1

Advanced Member level 5
Joined
Nov 18, 2008
Messages
2,123
Helped
596
Reputation
1,188
Reaction score
573
Trophy points
1,393
Location
Norwich, UK
Activity points
13,069
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
 
  • Like
Reactions: shaiko

    shaiko

    Points: 2
    Helpful Answer Positive Rating

shaiko

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,644
Helped
303
Reputation
608
Reaction score
297
Trophy points
1,363
Activity points
18,300
xenos,
It is a bad programming behavior to shift signed numbers
Can you suggest something that will work for signed numbers?
 

Tahmid

Advanced Member level 5
Joined
Jun 17, 2008
Messages
4,758
Helped
1,791
Reputation
3,574
Reaction score
1,651
Trophy points
1,393
Location
Silicon Valley, California, USA (from Dhaka, Bangl
Activity points
30,543
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.
 
  • Like
Reactions: shaiko

    shaiko

    Points: 2
    Helpful Answer Positive Rating

shaiko

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,644
Helped
303
Reputation
608
Reaction score
297
Trophy points
1,363
Activity points
18,300
Can you post a code example please?
 

xenos

Full Member level 4
Joined
May 9, 2015
Messages
212
Helped
82
Reputation
164
Reaction score
81
Trophy points
28
Location
127.0.0.1
Activity points
1,182
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;"
 
  • Like
Reactions: shaiko

    shaiko

    Points: 2
    Helpful Answer Positive Rating

horace1

Advanced Member level 5
Joined
Nov 18, 2008
Messages
2,123
Helped
596
Reputation
1,188
Reaction score
573
Trophy points
1,393
Location
Norwich, UK
Activity points
13,069
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
 
  • Like
Reactions: shaiko

    shaiko

    Points: 2
    Helpful Answer Positive Rating

FvM

Super Moderator
Staff member
Joined
Jan 22, 2008
Messages
48,940
Helped
14,339
Reputation
28,942
Reaction score
13,084
Trophy points
1,393
Location
Bochum, Germany
Activity points
282,369
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?
 
  • Like
Reactions: shaiko

    shaiko

    Points: 2
    Helpful Answer Positive Rating

zorro

Advanced Member level 4
Joined
Sep 6, 2001
Messages
1,131
Helped
357
Reputation
712
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,907
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
 
  • Like
Reactions: shaiko and FvM

    FvM

    Points: 2
    Helpful Answer Positive Rating

    shaiko

    Points: 2
    Helpful Answer Positive Rating

FvM

Super Moderator
Staff member
Joined
Jan 22, 2008
Messages
48,940
Helped
14,339
Reputation
28,942
Reaction score
13,084
Trophy points
1,393
Location
Bochum, Germany
Activity points
282,369
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.
 

Status
Not open for further replies.

Similar threads

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top