Fitting one integer in another

Question

You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (e.g., M becomes a substring of N located at i and starting at j).

EXAMPLE: Input: N = 10000000000, M = 10101, i = 2, j = 6 Output: N = 10001010100

whatever i tried so far-

int main()
{
    int m, n, i, j;
    printf("enter N\n");
    scanf("%d",&n);
    printf("enter M\n");
    scanf("%d",&m);
    printf("enter i\n");
    scanf("%d",&i);
    printf("enter j\n");
    scanf("%d",&j);

    int max = 1;
    int left = max-(( 1 << j)-1);
    int right = ((1 << j)-1);
    int mask = left | right;
    int ret = (n & mask)|(m << 1);
    printf("the answer is %d", ret);

}

but i am getting output-1215753963

If you're going to work with bits, it's generally wiser to use `unsigned` — pmg, Jun 28 '11 at 13:28
It looks to me like the input & output are the binary representations of your integers, not the decimal representations. With that said I haven't really looked in to the details of your code, but if you're typing in "10000000000" and "10101" and treating them like base-10 numbers, I doubt this is going to work out for you. — Mark Drago, Jun 28 '11 at 13:30
What happens if (1+j-i) != bitlen(M)? It seems like you only need one of i or j to do this if ALL of M is used. — RHSeeger, Jun 28 '11 at 13:31
Also, if they phrased the question that way, I'd ask what base the inputs are in. It *looks* like binary, but they could be anthing with a base >= 2. — 3Dave, Jun 28 '11 at 14:26

score 2 · Accepted Answer · edited May 23 '17 at 12:00

2

You are using the wrong format specifier in your printf call. %d prints it as an signed decimal integer. Here is a post on using printf to a binary format.

Coincidentally in binary the number you got is : 1011 0111 1000 1001 0001 0001 0001 0101

edited May 23 '17 at 12:00

Community

1
1

answered Jun 28 '11 at 13:28

Mike Kwan

24,123
12
63
96

RHSeeger · Answer 2 · 2011-07-01T00:05:05.350

1

Does the following work for what you need?

unsigned int fitint(unsigned int n, unsigned int m, int i, int j) {
    /*     bitwise not of (1s from j to the end) - (1s from i to the end) */
    unsigned int mask = ~ ( ((1 << (j-i)) - 1)   -    ((1 << i) - 1) );
    return (n & mask ) | (m << i);
}

Effectively:

Set the bits being modified to 0 via the mask
Set the bits being modified to the values of m via the | (m << i)

edited Jul 01 '11 at 00:05

answered Jun 28 '11 at 14:06

RHSeeger

16,034
7
51
41

i ll try this for sure..sorry for delay…i was out – learning_bee Jun 28 '11 at 23:33
how are u setting all bits to zero by a mask of all 1's. Please recheck. – Terminal Jun 30 '11 at 18:05
@Terminal - You're completely correct. That's the cost of posting code w/o trying it first. Updated with code that should work – RHSeeger Jul 01 '11 at 00:06

badawi · Answer 3 · 2011-06-29T02:56:23.603

I like your logic but there are a couple of mistakes:

Let me comment your code starting from int max = 1;. I am going to consider it as line # 1. The previous lines have been commented by Mike.

The first line is totally unnecessary.

Your logic is basically to create a mask that consists of 1's in all positions except from position i to position j.

To create a mask before j (i am moving from left to j), (based on your logic) you need the negative value of 2^j. Thus, the correct equation is int left = - (1 << (j+1)); . Why plus one because location j should be masked off.

To create a mask before i (i am moving from right to i), your logic is correct but you mistakenly typed j instead of i: int right = (1 << i) - 1;

Then, you joined these masks to construct the final mask as in line #4.

The last line before printf() should be int ret = (n & mask) | (m << i);. You again mistakenly typed 1 instead of i.

UPDATED:

Another way to implement your logic is as follows:

int maskoff = ((1 << (j - i + 1)) - 1) << i;
int ret = (n & ~maskoff) | (m << i);

score 0 · Answer 4 · answered Jun 28 '11 at 14:10

0

10000000000 in base 2 is 1024 in base 10

10101 in base 2 is 21 in base 10

So, you probably want

N = 1024; /* or from scanf */
M = 21;   /* but do not type numbers in base 2 */

before doing the bit masking and shifting.

answered Jun 28 '11 at 14:10

pmg

106,608
13
126
198

Fitting one integer in another

4 Answers4