The exercise is: Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.
My attempt at a solution is:
#include <stdio.h>
unsigned setbits(unsigned, int, int, unsigned);
int main(void)
{
printf("%u\n", setbits(256, 4, 2, 255));
return 0;
}
unsigned setbits(unsigned x, int p, int n, unsigned y)
{
return (x >>开发者_Go百科; (p + 1 - n)) | (1 << (n & y));
}
It's probably incorrect, but am I on the right path here? If not, what am I doing wrong? I'm unsure as to why I don't perfectly understand this, but I spent about an hour trying to come up with this.
Thanks.
Here's your algorithm:
- If n is 0, return x.
- Take 1, and left shift it n times and then subtract 1. Call this
mask
. - Left shift mask p times call this
mask2
. And
x with the inverse of mask2.And
y with mask, and left shift p times.Or
the results of those two operations, and return that value.
I think the answer is a slightly modified application of the getbits example from section 2.9.
Lets break it down as follows:
Let bitstring x be 1 0 1 1 0 0
Let bitstring y be 1 0 1 1 1 1
positions -------->5 4 3 2 1 0
Setting p = 4 and n =3
gives us the bitstring from x which is 0 1 1
. It starts at 4 and ends at 2 and spans 3 elements.
What we want to do is to replace 0 1 1
with 1 1 1
(the last three elements of bitstring y).
Lets forget about left-shift/right-shift for the moment and visualize the problem as follows:
We need to grab the last three digits from bitstring y which is 1 1 1
Place 1 1 1
directly under positions 4 3 and 2
of bitstring x.
Replace 0 1 1
with 1 1 1
while keeping the rest of the bits intact...
Now lets go into a little more detail...
My first statement was:
We need to grab the last three digits from bitstring y which is 1 1 1
The way to isolate bits from a bitstring is to first start with bitstring that has all 0s.
We end up with 0 0 0 0 0 0
.
0s have this incredible property where bitwise '&'ing it with another number gives us all 0s and bitwise '|'ing it with another number gives us back that other number.
0 by itself is of no use here...but it tells us that if we '|' the last three digits of y with a '0', we will end up with 1 1 1. The other bits in y don't really concern us here, so we need to figure out a way to zero out those numbers while keeping the last three digits intact. In essence we need the number 0 0 0 1 1 1
.
So lets look at the series of transformations required:
Start with -> 0 0 0 0 0 0
apply ~0 -> 1 1 1 1 1 1
lshift by 3 -> 1 1 1 0 0 0
apply ~ -> 0 0 0 1 1 1
& with y -> 0 0 0 1 1 1 & 1 0 1 1 1 1 -> 0 0 0 1 1 1
And this way we have the last three digits to be used for setting purposes...
My second statement was:
Place 1 1 1 directly under positions 4 3 and 2 of bitstring x.
A hint for doing this can be found from the getbits example in section 2.9. What we know about positions 4,3 and 2, can be found from the values p = 4 and n =3
. p is the position and n is the length of the bitset. Turns out p+1-n
gives us the offset of the bitset from the rightmost bit. In this particular example p+1-n = 4 +1-3 = 2
.
So..if we do a left shift by 2 on the string 0 0 0 1 1 1
, we end up with 0 1 1 1 0 0
. If you put this string under x, you will notice that 1 1 1
aligns with positions 4 3 and 2
of x.
I think I am finally getting somewhere...the last statement I made was..
Replace 0 1 1 with 1 1 1 while keeping the rest of the bits intact...
Lets review our strings now:
x -> 1 0 1 1 0 0
isolated y -> 0 1 1 1 0 0
Doing a bitwise or on these two values gives us what we need for this case:
1 1 1 1 0 0
But this would fail if instead of 1 1 1
, we had 1 0 1
...so if we need to dig a little more to get to our "silver-bullet"...
Lets look at the above two strings one more time...
x -> bit by bit...1(stays) 0(changes) 1(changes) 1(changes) 0(stays) 0(stays)
So ideally..we need the bitstring 1 x x x 0 0
, where the x's will be swapped with 1's.
Here's a leap of intuition that will help us..
Bitwise complement of isolated y -> 1 0 0 0 1 1
& this with x gives us -> 1 0 0 0 0 0
| this with isolated y -> 1 1 1 1 0 0 (TADA!)
Hope this long post helps people with rationalizing and solving such bitmasking problems...
Thanks
Note that ~0 << i
gives you a number with the least significant i
bits set to 0
, and the rest of the bits set to 1
. Similarly, ~(~0 << i)
gives you a number with the least significant i
bits set to 1
, and the rest to 0
.
Now, to solve your problem:
- First, you want a number that has all the bits except the
n
bits that begin at positionp
set to the bits ofx
. For this, you need a mask that comprises of1
in all the places except then
bits beginning at positionp
:- this mask has the topmost (most significant) bits set, starting with the bit at position
p+1
. - this mask also has the least significant
p+1-n
bits set.
- this mask has the topmost (most significant) bits set, starting with the bit at position
- Once you have the above mask,
&
of this mask withx
will give you the number you wanted in step 1. - Now, you want a number that has the least significant
n
bits ofy
set, shifted leftp+1-n
bits.- You can easily make a mask that has only the least significant
n
bits set, and&
it withy
to extracty
's least significantn
bits. - Then, you can shift this number by
p+1-n
bits.
- You can easily make a mask that has only the least significant
- Finally, you can bitwise-or (
|
) the results of step 2 and 3.2 to get your number.
Clear as mud? :-)
(The above method should be independent of the size of the numbers, which I think is important.)
Edit: looking at your effort: n & y
doesn't do anything with n
bits. For example, if n
is 8, you want the last 8 bits of y
, but n & y
will just pick the 4th bit of y
(8 in binary is 1000). So you know that can't be right. Similarly, right-shifting x
p+1-n
times gives you a number that has the most significant p+1-n
bits set to zero and the rest of the bits are made of the most significant bits of x
. This isn't what you want either.
精彩评论