Bitwise Manipulation or Bitwise Programming [closed]

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

I know the concepts of bit-wise operators, bit manipulation, 2's complement etc. But when it comes to solving something using bit manipulation it does not strike me. I takes me time to wrap my head around them.

I thought it would help if I looked at some questions regarding bit operators/bit manipulation but it left me even more confused as to how to approach this topic. I am not looking for an answer to a specific problem but a generalized approach / mindse开发者_运维知识库t while tackling bit manipulation. Thanks.

---

Answers given so far are nowhere near useful. But the link given by Naveen helped me a bit. Quite a lot of examples given here. I am trying to learn from them. Maybe it'll help others.

Bit Hacks

UPDATE: I have been going through the examples given in the link above. They were good. Also I stumbled on - Resource for Bitwise Programming link in SO. Excellent Resource. After going through all those resources I feel bitwise programming is easy! Never thought I would use that in a sentence :)

---

I divine your question to be:

What approach should I take, and what mindset should I adopt, when tackling problems involving bit manipulation ?

If that is correct, read on, if not, stop now ...

Bit manipulation is a difficult topic for the beginner such as me. I will have to concentrate hard and pay careful attention as I work through a graded set of sample problems. I will revise what I learn at regular intervals.

---

But when it comes to solving something using bit manipulation it does not strike me

"Think a C variable as a binary string, and data is represented by this binary string"

I built an example program that illustrates operations on bits in a very simple manner, I started with this example to manipulate certain bits of variables and to realize the changes made with the helper function dec2bin(number, size_of_the_data).

We can learn very easy, bit operations using illustrative binary part of the variable (data). For example if we have a variable character (char) which contains the ASCII character 'b' to make to a capital character 'B', we will need to manipulate bit number 6 (remember that type char has 8 bits available (depends on system architecture)) from 1 to 0, a first in mind operation is expressed as c xor 0x20 (for C language expression will be c ^ = 0x20);

Explanation:

b - 0110 0010 - to uppercase B - 0100 0010 (how?)

We will need to handle bit number six which is set to true (lowercase) to false which will translate content of variable to a capital character. Looking at truth tables AND, OR, XOR, NOT the truth table which we will choose will be XOR truth table because of logical theory property 1 xor 1 result in 0 bit value, in C this operation is expresed as ^. What about 0x20 is a hexadecimal mask in binary (2) 0010 0000 (0), that expression represent 0110 0010 xor 0010 0000 => 0100 0010 is a capital character 'B'. We will observe that capital character 'B' xor mask will result in a lowercase character 'b'.

Playing with this program we will find that bitwise operations are very easy to understand.

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

void dec2bin(signed long long int, unsigned short size);

int main()
{
    signed long long int packedData = 0xABC4F0DE;

    signed long long int testData = -0xFF;
    dec2bin(testData, sizeof(signed long long int));

    /*
     *  NOTE:
     *  -----
     *  All printed instructions are virtually and are garbage
     *  instructions (not used anywhere in programming).
     *  That instructions are supposed to make current operation visible.
     */
    //Garbage data (random which calls for a global complex subroutine)
    printf("Istruction  1: [RND [__global__]     ] ");
    dec2bin(packedData, sizeof(unsigned long int));

    // NULL the data - CLR (clear all bits from data)
    // CLR is calling a sobroutine composed with AND 0x0 mask;
    packedData &= 0x0;
    printf("Istruction  2: [CLR [AND 0x0]        ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Adding 0x3A (0011 1010) to packed data
    packedData |= 0x3A;
    printf("Istruction  3: [OR  0x3A             ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Shift to the left this data to next nibble
    packedData <<= 4;
    printf("Istruction  4: [SHL 0x4              ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Shift again to the left this data to next nibble
    packedData <<= 4;
    printf("Istruction  5: [SHL 0x4              ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Adding 0xF (1111) to packed data
    packedData |= 0xF;
    printf("Istruction  6: [OR  0xF              ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Shift again to the left this data to next byte (2 * nibble)
    packedData <<= 8;
    printf("Istruction  7: [SHL 0x8              ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Extract contents of low ordered nibble from second byte (with a mask)
    packedData &= 0x00000F00;
    printf("Istruction  8: [AND 0x00000F00       ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Invert (negate|NAND) each bit from data (invert mask)
    packedData = ~packedData;
    printf("Istruction  9: [INV [NOT XXXXXXXX]   ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Shift to the right this data to previous nibble
    packedData >>= 4;
    printf("Istruction 10: [SHR 0x4              ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Shift to the right this data to previous nibble
    packedData >>= 4;
    printf("Istruction 11: [SHR 0x4              ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Shift to the right this data to previous nibble
    packedData >>= 2;
    printf("Istruction 12: [SHR 0x2              ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Invert (negate|NAND) each bit from data (invert mask)
    packedData = ~(packedData) & 0x00FFFFFF;
    printf("Istruction 13: [INV [NAND 0x00FFFFFF]] ");
    dec2bin(packedData, sizeof(signed long int));

    // Adding 0xF0000000 (1111 0000 ... 0000) to packed data
    packedData |= 0xF0000000;
    printf("Istruction 14: [OR  0xF0000000       ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Shift to the left this data to next nibble
    packedData <<= 4;
    printf("Istruction 15: [SHL 0x4              ] ");
    dec2bin(packedData, sizeof(signed long int));

    // Exclusive or
    packedData ^= 0x0F0000F0;
    printf("Istruction 16: [XOR 0x0F0000F0       ] ");
    dec2bin(packedData, sizeof(signed long int));

    return 0;
}

void dec2bin(signed long long int number, unsigned short size)
{
    int c, k;
    for (c = (size*8)-1; c >= 0; c--)
    {
        k = number >> c;
        if (k & 1)
            printf("1");
        else
            printf("0");
        if (c % 4 == 0)
            printf(" ");
    }
    printf("\n");
}

---

So what exactly are you looking for, this looks kind of vague to me to be honest. Have you ever read a book about for example C? You could look up some code examples on how to approach some standard programming solutions in C perhaps.

---

I learned a lot about this by writing my own compact, cross-platform binary protocol for sending object messages over a stream (suck as a network socket).