CODEWITHSUNDEEP
c++bit-manipulation
user3444650
user3444650

Reputation: 117

Replacing front bits of an int

Replace the first x bits of an int given:

  1. number of bits to replace
  2. a new bit sequence

e.g: replacing first 4 bits with 5 bit sequence (1100 -> 10111)

1100 0010 1001 -> 1 0111 0010 1001

I know how to flip the bits if they're the same length using std::bitset but how can I do it if the sequence is less or more than the first sequence?

Edit: To clarify, I need to replace a certain number of most significant bits with another certain number of bits. I don't need an algorithm to check if the int is too short to replace 4 bits, I'll handle that. I just need to cut off x bits and contcatenate y bits, given an int (which is converted to bits)

Upvotes: 1

Views: 561

Answers (5)

J.Baoby
J.Baoby

Reputation: 2231

If you want to replace the first x bits (in my code I used size_repl instead of x) of an integer n with some new bitsequence new_bits you can use this function (suppose the function first_set returns the first bit that is set):

int replace_first_bits(unsigned int n, int size_repl, int new_bits){
    int first = first_set(n);
    if (first < 0){
        //if no bit is set in n => n = 0 => return new_bits (CHANGE IF NECESSARY)
        return new_bits; 
    }

    //replace bits `first` untill `(first+size-1)` => bits from `first+size` untill last bit stay the same
    int mask_size = (sizeof(unsigned int) << 3) - (first+size_repl);
    if (mask_size < 0){
        // size_repl is greater than the length of n in binary notation 
        //     => replace much more than what is used => just replace everything (CHANGE IF NECESSARY)
        return new_bits;
    }
    int mask = (1 << mask_size) - 1;
    return (new_bits << mask_size) + (n & mask);
}

I've implemented first_set like this: 

int first_set(unsigned int i){
    int count = sizeof(unsigned int) << 3;
    unsigned int n = i;
    while(n){
        n = n >> 1;
        count--;
    }
    return count;
}

You'll probably notice I've used unsigned int instead of int. That's because in the case of a (signed) int if it is negative, the first bit will be 1.

Another thing I'll add is that I considered the most left bit as being bit 0 and the most right bit as being bit 31 (for a 32-bit integer). By using sizeof(unsigned int) I'm sure this code will work for any size of int.

Here is a demo of the code with the example you gave: replace first 4 bits of 1100 0010 1001 (= 3113) with 10111 (= 23).

Hope it helps.

PS: last line in the output of the demo is something that helped me count the indices of the bits in a bitsequence.

Upvotes: 0

Saurav Sahu
Saurav Sahu

Reputation: 13924

Result = [ Input-Pattern | Remains-after-MSBs-Trimmed-Out ]

You can find the highest set bit (hsb) using floor(log2(n)) and number of bits in the input number x using numeric_limits<T>::digits. 

size_t afterBitPos = floor(log2(x)) - numOfBitsToBeReplaced + 1;
size_t numberOfBits = (std::numeric_limits<unsigned>::digits - floor(log2(x)) - 1 + numOfBitsToBeReplaced );

//Clear "numberOfBits" MSBs
x <<= numberOfBits;
x >>= numberOfBits;

pattern <<= afterBitPos; //Position them in MSB positions.

x = x | pattern;

Live demo.

Upvotes: 0

Jahangir Alam
Jahangir Alam

Reputation: 801

I can not remember required C++ functions to do this, but I can write the algorithm to achieve your desired output. 

let,
int x = 0;
int n = 2; //number of bits to be replaced
int num = 11010; // 32 bit number to be manipulated with leading 0's
int unchanged_bits = bit seq length of num - n  
bit_seq = 101; so 11 will be replaced by 101 and 010 will be unchanged

do left shift x unchanged_bits times and add 1 each time // you will get 111 with leading 0's

now do logical & between num and 111 // you will get num with unchanged bits 010 with leading 0's

now left shift the given bit_seq 3 times// since length of 010 is 3 and you will get 101000

Now do logical OR between 101000 and 010 with leading 0's

Thus you will get desired output

Upvotes: 0

stefaanv
stefaanv

Reputation: 14392

Either first means from a certain position in the bit-sequence that is considered the highest significant bit (hsb), meaning that first must be given to know where to operate and first will change since the sequence will contain more or less bits.
Or first means the least significant bit (lsb), in which case a left/right shift is needed to change the sequence to replace so it has the same size as the new sequence.

00000100100011101001  
     ^hsb          ^lsb (which is actually first?)

BTW: if you want your sequence to grow without specifying when constructed, you might want to check out boost.dynamic_bitset

Upvotes: 1

Violapterin
Violapterin

Reputation: 347

maybe you can....?

std::size_t x =3113; // which is 1100 0010 1001
std::size_t y =x%256; // remain of 2^8
x =y +23 *256; // add 1 0111 0000 0000

Upvotes: 0

Related Questions