Bit Manipulation Problems

Define the following: bitmask,bitstring

Answer:
- bitstring An arbitrary number of bits. Also called a bit vector.
- bitmask A bitstring string that's meant to select certain bits out of a bit string.
Write a C++ function which will cause bit i of an int value to be set to 1, leaving all other bits unchanged. Call this function setBit which has the following prototype:
```
  void setBit( unsigned int & num, int index ) ;
```
You may assume the index is between 0 and 31 inclusive. As usual, index 0 is the least significant bit (LSb), while index 31 is the most significant bit.
Answer:
```
void setBit( unsigned int & num, int index ) {
   unsigned int bitMask = 1 ;  // Set LSb to 1
   bitMask <<= index ;         // Set bit_index to 1, by shifting 
   num |= bitMask ;            // OR in correct value
}
```
Write a C++ function which will cause bit i of an int value to be set to 0, leaving all other bits unchanged. Call this function clearBit, with the following prototype:
```
  void clearBit( unsigned int & num, int index ) ;
```
You may assume the index is between 0 and 31 inclusive. As usual, index 0 is the least significant bit (LSb), while index 31 is the most significant bit.
Answer:
```
void clearBit( unsigned int & num, int index ) {
   unsigned int bitMask = 1 ;
   bitMask <<= index ;
   bitMask = ~bitMask ;  // Flip bits
   num &= bitMask ;      // AND in the correct bit
}
```

Write a C++ function called anyBitInRangeSet that will determine if at least one bit from index low to high (where low <= high) of a number called num are set to 1. It should return true if so, and false if all are 0's.

Here's the prototype:

  bool anyOnes( unsigned int & num, int low, int high ) ;

Answer:

bool anyOnes( unsigned int & num, int low, int high ) {
   int numOnes = ( high - low ) + 1 ;
   unsigned int bitMask = ~0 ;  // Flip 0 to get all 1's
   bitMask <<= numOnes ;        // Now create numOnes zeroes at the end
   bitMask = ~bitMask ;         // Flip bits to numOnes 1's
   bitMask <<= low ;            // Shift low bits to left

   return num & bitMask ;      // true, if num & bitMask is non-zero
}

Write a C++ function that leaves all bits low to high (where low <= high) of a number called num alone, and sets all bits outside the range to 0.

Here's the prototype:

bool selectRange( unsigned int & num, int low, int high ) {

Answer:

bool selectRange( unsigned int &num, int low, int high ) {
   int numOnes = ( high - low ) + 1;
   unsigned int bitMask = ~0 ;  // Flip 0 to get all 1's
   bitMask <<= numOnes ;        // Now create numOnes zeroes at the end
   bitMask = ~bitMask ;         // Flip bits to numOnes 1's
   bitMask <<= i ;              // Shift low bits to left

   return num &= bitMask ;      // true, if num &= bitMask is non-zero
}

Write a C++ function that swaps num1 and num2 without using a temporary variable. Hint: use the XOR operator (which is the carat operation).
Answer:
```
void swap( unsigned int &num1, unsigned int &num2 ) {
   num1 = num1 ^ num2;  // num1 holds num1' XOR num2'
   num2 = num1 ^ num2;  // num2 holds num1' XOR num2' XOR num2' == num1'
   num1 = num2 ^ num1;  // num1 holds num1' XOR num1' XOR num2' == num2'
}
```
Let num1' be the original value of num1, at the time it was passed in. Let num2' be the original value of num1, at the time it was passed in.

Assume that your compiler does a logical right shift with operator: >>. That is, it fills the values with 0. Write a function which takes two ints as a parameter. The first is a 32 bit signed int, num, passed in by reference, and the second is an int, which is the number of bits to shift right. This will perform an arithmetic right shift.

Answer:

void arithmeticRightShift( unsigned int & num, int shiftAmt ) {
  unsigned int bitMask = 1;

  bitMask <<= 31 ;        // assume 32 bits--puts 1 at MSb
  if ( bitMask & num )    // is num negative?
    {
       bitMask = ~0 ;     // make all 1's by negating 0
       bitMask << ;= ( 32 - shiftAmt );
       num >>= shiftAmt;  // Shift right
       num |= bitMask;    // Put 1's in upper shiftAmt bits of num
    }
  else // num is non-negative
    num >>= shiftAmt;     // use regular logical shifting
}

Web Accessibility