Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronic 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.

Register Log in

When does this function exit

Status
Not open for further replies.

shaiko

Advanced Member level 5
Joined
Aug 20, 2011
Messages
2,641
Helped
302
Reputation
606
Reaction score
297
Trophy points
1,363
Activity points
18,255
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,071
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,641
Helped
302
Reputation
606
Reaction score
297
Trophy points
1,363
Activity points
18,255
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:
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.
 
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
356
Reputation
710
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,902
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,071
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,641
Helped
302
Reputation
606
Reaction score
297
Trophy points
1,363
Activity points
18,255
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,649
Trophy points
1,393
Location
Silicon Valley, California, USA (from Dhaka, Bangl
Activity points
30,545
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,641
Helped
302
Reputation
606
Reaction score
297
Trophy points
1,363
Activity points
18,255
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,071
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
47,436
Helped
14,034
Reputation
28,321
Reaction score
12,684
Trophy points
1,393
Location
Bochum, Germany
Activity points
275,912
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
356
Reputation
710
Reaction score
298
Trophy points
1,363
Location
Argentina
Activity points
8,902
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
47,436
Helped
14,034
Reputation
28,321
Reaction score
12,684
Trophy points
1,393
Location
Bochum, Germany
Activity points
275,912
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.
Toggle Sidebar

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Top