how to express logical and bitwise shift operations in C.

[LSD]

Hi.

I'm looking for some exercises to prepare myself for an exam in basic c programming.

I've found one now that seems like a good one:

The binary logarithm of n (log₂n) is the power to which the number 2 to must be raised to obtain the value n. Write a C function that calculates log₂ of an unsigned integer n using the following approach: find the most significant set bit in n and return the position of this bit. For example, if n is 17 (0b10001), the function should return 4.

To solve this problem you need to read up on how to express logical and bitwise shift operations in C.

Here's my attempt:

First, I'm thinking I have to count the input (scanf) number's bits, and print that number. What I mean by this is the following:

If the input number is 22, the binary number is 0b11000. If I count those numbers, I end up with 5. But since the first position starts with 0, I should get 5-1 = 4.

Can you guide me somehow on how to solve this? I'm familiar with shift operations (22 >> 2 = 0b110) but my knowledge is very limited.

[stahta01]

I suggest writing some code. Announcements - General Programming Boards

Then ask for help.

I suggest a while or a for loop.

Tim S.

[LSD]

I thought I could get some help applying my thoughts in code form, heh.

Anyhow. I've searched a bit on the Internet for answers, but no one appeared to include the scanf function. Whatever I'm doing, I get the same output.

int main(){
unsigned int i, k; // i is input, k is output.
scanf("%d", i);
k = (i & -i);
printf("%d", k);
}

I can't see how I can use a for or while loop. I was thinking that early on, if I could somehow translate my number into a binary number, then count if number is 0, go to next, if 0, go to next, if 1, print number of loops. But that would only work if I only had the leftmost bit as 1, and all the rest were 0.

Thanks for replying.

[Matticus]

If the input number is 22, the binary number is 0b11000.

22 in binary is 10110 (16+4+2). The value you provided is decimal 24 (16+8). Take care that you are using the correct values, else your test might appear to fail when it actually succeeds.

To solve this problem you need to read up on how to express logical and bitwise shift operations in C.

The code you provided does not use any bitwise shifting.

main.c||In function 'main':|
main.c|6|warning: format '%i' expects type 'int *', but argument 2 has type 'unsigned int'|
main.c|6|warning: 'i' is used uninitialized in this function|
||=== Build finished: 0 errors, 2 warnings ===|

You have some basic problems with that code that need to be fixed before continuing.

[LSD]

22 in binary is 10110 (16+4+2). The value you provided is decimal 24 (16+8). Take care that you are using the correct values, else your test might appear to fail when it actually succeeds.

Of course, careless mistake, thank you for pointing it out.

The code you provided does not use any bitwise shifting.

I know, because I don't understand the use of it in this particular problem.

An idea that struck my mind as I'm writing this. Can it be possible to write, as previously suggested, a for or while loop that does the bitwise shift operation once per loop until the number is 0? Or am I still wrong?

Thanks a lot for your help, really appreciated.

[Matticus]

An idea that struck my mind as I'm writing this. Can it be possible to write, as previously suggested, a for or while loop that does the bitwise shift operation once per loop until the number is 0?

This is one approach. In fact, I recently wrote something along those lines for a microcontroller to send bytes serially, bit by bit, to an external memory chip.

You really should be working this out on paper, to see how you need to manipulate the bits, in order to solve the problem.

[LSD]

This is one approach. In fact, I recently wrote something along those lines for a microcontroller to send bytes serially, bit by bit, to an external memory chip.

You really should be working this out on paper, to see how you need to manipulate the bits, in order to solve the problem.

I'll get right on it.

We've just started µcontrollers (STK or something). A lot more fun to be honest, heh. Also, I'm writing down my thought process in my book, but where I fail is translating my solution paper into code. I sometimes think too advanced, and sometimes I don't think at all, unfortunately.

It's going much better now. I'll post my progress soon.

[Matticus]

Excellent. Have you ever heard of the term "masking" in the context of binary?

[LSD]

Excellent. Have you ever heard of the term "masking" in the context of binary?

I've heard of it, yes, but I can't explain it. It has something to do with masking binary numbers to 1 or 0 by performing logical bitwise operations - I think.

Here's my new attempt at a code:

int main(){


unsigned int i, k = 0; // i is input, k is output.


printf("Enter your number: ");
scanf("%d", i);


	while(i >= 1){     //as long as i is bigger than 0, the loop should run
	i = i >> 1;          //take the input i, and perform bitwise right operation (0b10110) should be (0b01011) for instance. 
	k = k++;           //k+1 every loop - counts the loops. (0b10110) -> (0b01011) -> (0b00101) -> (0b00010) -> (0b00001) ->(0b00000) -> program runs for 5 loops
	}

k = k - 1;


printf("%d", k);


}

My output is 21, and 21 only. I'm confused.

[Matticus]

Again, let me stress that your code needs to be correct, before you can even start to solve this problem.

scanf("%d", i);  // <--- this is incorrect

scanf("%u",&i);  // <--- try this instead

k = k++;  // <--- this is incorrect

k++;  // <---this is what you should have

[stahta01]

You need to compile with warnings on; then you need to read the warnings.
DO NOT IGNORE WARNINGS.

First of several warnings, I got with your code.

warning: format '%d' expects argument of type 'int *', but argument 2 has type 'unsigned int' [-Wformat=]
 scanf("%d", i);

Tim S.

[LSD]

Thanks a lot to both of you. Turns out I've been careless.

Also, I have warnings on, but my compiler seems to only post errors. I'm not too sure where I can check if my warnings are really on, or if I just think they are. What I can say, though, is that I've had warnings in the past.

I really appreciate your help. If nothing else, I've learned that I have to spend more time programming at the beginning stage that I'm on, to make sure that mistakes like these doesn't waste my time.

[laserlight]

Also, I have warnings on, but my compiler seems to only post errors. I'm not too sure where I can check if my warnings are really on, or if I just think they are. What I can say, though, is that I've had warnings in the past.

Which compiler (and IDE, if applicable) are you using?

[LSD]

I'm using cygdrive to compile my codes. I'm not sure what you mean by IDE, I'm afraid.

[laserlight]

cygdrive is not a compiler. However, by mentioning it, it means that you are using cygwin, which in turn implies that you are probably using gcc as your compiler. If so, you should refer to the GCC manual on Options to Request or Suppress Warnings. Typically, options like -Wall and -pedantic would be used.