Find set bits and shift them to left most position using 32 bits

Question

I am trying to figure out how to find all set bits in a hex number and then shift those bits to the left most positions using a 32 bit notation.

My program reads in args from the command prompt and then calls the appropriate function and passes either the 3rd or both 3rd and 4th args into the chosen function.

Here is my code so far:

#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>

void printBits(unsigned long num){
    //Function to display a hexidecimal number in binary
    //Precondition: num is in hex notation
    //Postcondition: num is displayed in binary notation
    int i;
    int count = 1;
    unsigned long mask = 0x80000000;
    for (i = 1; i <=32; i++){
        int out = num & mask;
        num = num << 1;
        if (out ==0){
            printf("%u",0);
        }
        else{
            printf("%u",1);
        }
        if (count ==4){
            printf(" ");
            count = 0;
        }
        count++;
    }
    printf("\n");
}

void setUnion(unsigned long a, unsigned long b){
    //Function to display the union of 2 hexidecimal numbers
    //Precondition: a and b are both hexidecimal numbers
    //Postcondition: a is OR'd with b and the appropriate solution is displayed
    printBits(a|b);
}

void setIntersection(unsigned long a, unsigned long b){
    //Function to determine the intersection of two hexidecimal numbers
    //Precondition: a and b are both in hex format
    //Postcondition: a and b are compared using the & operator and the appropriate solution is displayed
    printBits(a&b);
}

void setComplement(unsigned long a){
    //Function to find the one's compliment of a give hex
    //Precondition: a is a hexidecimal number
    //Postcondition: the complement of a is displayed
    printBits(~a);
}

void countSet(unsigned long a){
    //Function to count the number of set bits in a
    //Precondition: a is a hexidecimal number
    //Postcondition: number of set bits are counted and count is displayed to user
    unsigned int count; // count accumulates the total bits set in a
    for (count = 0; a; count++){
        a &= a - 1; // clear the least significant bit set
    }
    printBits(a);
    printf("Number of bits set is ");
    printf("%i",count);
}

void setRotate(unsigned long x, unsigned long y){
    //Function to perform a rotation of bits to the right
    //Precondition: x is in hex form and will be rotated by y places to the right
    //Postcondition: x is displayed with bits rotated y positions to the right
    unsigned long num;
    num = (x >> y)|(x << (32 - y));//code obtained from geeksforgeeks.com, author unknown, date of publishing unknown
    printBits(num);
}

void shiftSet(unsigned long x){
    //Function to shift all set bits to the left
    //Precondition: x is a hexidecimal number
    //Postcondition: all set bits in x are shifted to the left most bit placements

    unsigned int count;
    for (count = 0; x; count++){
        x &= x - 1; // clear the least significant bit set
    }

    printBits((1 << (count % 32))+1);
}

int main(int argc, char *argv[]) {
    unsigned long x;
    unsigned long y;
    char invoke_command[] = ("lab2");
    if (argc != 3 && argc != 4){
        printf("Arguments incorrect, please provide 3 or 4 arguments");
        printf("\n");
        exit(0);
    }
    else {
        sscanf(argv[2], "%x", &x);

        switch(argv[1][1]){

            case 'p':
                printBits(x);
                break;
            case 'u':
                sscanf(argv[3], "%x", &y);
                setUnion(x,y);
                break;
            case 'i':
                sscanf(argv[3], "%x", &y);
                setIntersection(x,y);
                break;
            case 'c':
                setComplement(x);
                break;
            case 'r':
                sscanf(argv[3], "%i", &y);
                setRotate(x,y);
                break;
            case 's':
                countSet(x);
                break;
            case 'm':
                shiftSet(x);
                break;
        }
    }
    return 0;
}

I'm am very new to C and am not very good at bit operators. My shiftSet function is what I am having difficulty with. Currently it is shifting all set bits to the right and I can't figure out how to make it go left. If anyone can offer any suggestions, I would greatly appreciate it. Also this is my first post here, so I screwed up the preferred format I apologize.

Basically what I am looking for is this: Pass in 0x55 (0000....0101 0101) and get (1111 0000.....0000).

This is a HW problem and I did speak with my professor about this issue and let's just say that his advice was not very helpful.

Answer 1

What about:

void shiftSet(unsigned long x){
    //Function to shift all set bits to the left
    //Precondition: x is a hexidecimal number
    //Postcondition: all set bits in x are shifted to the left most bit placements

    unsigned int count;
    for (count = 0; x; count++)
        x &= x - 1; // clear the least significant bit set

    unsigned long u = ~0UL;
    if (count == 0)
        u = 0;
    else if (count < 32)
        u = (u >> (32 - count)) << (32 - count);

    printBits(u);
}

It would have been nice to be able to use a function to count the bits, but your countBits() function is inextricably intertwined with the I/O and does not return a value, so it can't be reused.

Answer 2

The first problem is the count % 32. That's going to treat 0 and 32 as essentially the same. You do need to limit the shift value to a number between 0 and 31 to avoid undefined behavior. But you can't treat 0 and 32 as the same thing, so one of those needs to be handled as a special case.

The other issue is the (1 << n) + 1. That's going to set at most 2 bits. I suggest starting with 0xffffffff, and then see if you can figure out how to shift it so that you come up with the correct answer.

BTW, I tested your method for counting the bits, and it appears to work, good job!