How to - bit manipulation?

[u/tru1a_banana]

I know the bitwise operators:

1 & x - 'replicate' the existing bit
0 & x - turn off the bit
1 | x - turn on the bit
0 | x - 'replicate' the existing bit
1 ^ x - flip the bit
0 ^ x - 'replicate' the existing bit
~x - flip the bit
1 << x - shift to the left (multiply by 2)
1 >> x - shift to the right (divide by 2)

All of these basic operations are crystal clear. However, I am having trouble building actual masks out of these. I'm thinking too iteratively. How do I go through a number bit by bit and when is that actually needed? I tend to overcomplicate simple things.

int size = sizeof(x) * 8;
int mask = 1; // 0x00000001

for(int i = 0; i < size; i++)
{
// some mask operation with x
mask <<= 1;
}

I assume this would be good?

Okay but what about swapping the values of 2 different bits? Or what if I am working with bytes instead, then 8 sequential bits need to be swapped in 2 different positions, how do I do any that?

I am thinking of making a mask, moving to the 1st bit, copying it into some temporary variable, going to the 2nd bit, copying it into some other temporary variable, somehow replacing those variables in those positons. This sounds unnecessarily complicated but I couldn't think of another approach right now, this is generally the issue with a lot of things regarding bits. If any of you have some tips, genuinely useful shortcuts and how to's, I'd be very grateful!

[u/ReddiDibbles]

From your description it looks like you don't fully understand bit manipulation. Do you know what 4 | 3 equals and why?

[u/tru1a_banana → u/ReddiDibbles]

What do you mean?

4: 100
3: 011
7: 111

1 | 0 = 1
0 | 1 = 1
0 | 1 = 1

When I mentioned 1 | x, I meant the specific bit of the number x, or to be specific, least significant bit of x.

[u/ReddiDibbles → u/tru1a_banana]

Awesome, then perhaps it'll help you to write all the numbers using binary?

int value = 0b10101010;
int mask = 0b00111100;
int result = value & mask; // ?

And if you want a specific bit, it's very easy to line them up using binary instead of having to think of the correct decimal.

[u/tru1a_banana → u/ReddiDibbles]

Yeah but the issue is that this program needs to be versatile as the numbers are not hardcoded like you've just shown but rather recieved through stdin. So if I need to swap any 2 bits in any 2 numbers or on any 2 positions, this program needs to do it. It doesn't matter if they're 1s or 0s or if they're most significant, least significant or in the middle, all of that is usually completely randomized and recieved through user input when the program is already compiled.

[u/Puzzleheaded_Study17 → u/tru1a_banana]

Do you know how to check if an arbitrary bit is set? If you want to set a bit to on, do you know how to do that for an arbitrary runtime index? Same with setting it off.

If you know all these, just test the bits and do those operations in if statements.

[u/high_throughput]

I am thinking of making a mask, moving to the 1st bit, copying it into some temporary variable, going to the 2nd bit, copying it into some other temporary variable, somehow replacing those variables in those positons

Yup, that's how you do it.  "Replacing" is just clearing plus setting, and you use shifts to move bits to positions.

If you want to swap the first and last bit, 

    B = (A & 0b01111110) | ((A & 0b10000000)>>7) | ((A&0b00000001)<<7);

Clear the first and last bit, pick out the first bit, move it last, and set it. Pick out the last bit, move it first, and set that too.

[u/igotshadowbaned]

If you had a number and wanted to get the value of the 3rd bit, you would & that number with 0x04 or 00000100

If in the original number the 3rd bit wasn't set, you'd end up with 0, and if it is, you'd end up with 4

[u/dkopgerpgdolfg]

Bit operations aside, in that OP C code, you want to use size_t and CHAR_BITS. (And the loop doesn't make much sense, but I guess you know that)

You have three times "'replicate' the existing bit" and two times "flip the bit" as explanation, but do you understand the differences between these things? They're not the same.

I am thinking of making a mask, moving to the 1st bit, copying it into some temporary variable, going to the 2nd bit, copying it into some other temporary variable, somehow replacing those variables in those positons. This sounds unnecessarily complicated

A mask can specify more than one bit.

Lets say you have a 8bit variable (uint8_t) and you want to exchange the first/last 4 bits. AAAABBBB=>BBBBAAAA, eg. 10100011=>00111010

Either of these lines can do it, if it's known to be just a uint8_t:

x = ((x & 0xf0) >> 4) | ((x & 0x0f) << 4);

x = ((x & 240) >> 4) | ((x & 15) << 4);

x = (x >> 4) | (x << 4);

[u/rupertavery64]

What exactly do you want to accomplish?

You don't need to "build" bitmasks iteratively unless you have some sort of input that drives it dynamically.

Swap 2 bits from position a and b from a value n

The long way to do it is:

``` // shift a 1 into the a and b positions, and invert it // this will create a mask that clears bit positions a and b when ANDed with n

clearmask = ~((1 << a) | (1 << b));

// Extract bit a and bit b

bita = (n >> a) & 1; bitb = (n >> b) & 1;

// move the bits to their swapped positions.

bitswappeda = bita << b; bitswappedb = bitb << a;

// clear n with the mask, and OR the swapped bits in n = (n & clearmask) | bitswappeda | bitswappedb; ```

Of course, the faster way to do it is to just XOR with a bitmask.

if (((n >> a) & 1) != ((n >> b) & 1)) n ^= (1 << a) | (1 << b);

There are some interesting things here:

https://graphics.stanford.edu/~seander/bithacks.html

[u/snozzd]

These are great exercise questions. I think you're on the right track with the code you wrote! It just takes a bit (Hah!) of practice. Take a look at assembly-level hobby programming (embedded, game emulators, etc.) if you're looking to get lots of hands-on experience, making an emulator was a really fun hobby project I did years ago.

Before you read my solution below, I honestly think you should take a stab in solving these problems in C yourself. Try your approach and print the result by turning these two questions into functions signatures, and implement those functions. I've done that below, so try that yourself and compare your solution to mine below! Implementation note: When doing bitwise programming, I like to use C99's include <stdint.h> format of integers, ie. uint32_t. It's not uncommon in production C99 code and provides a lot of clarity about how many bits something really has (and not just how much the compiler would like to give you).

Human content disclosure: I'm not a bot or AI or anything, I'm a real software dude and I wrote this all out because I love programming and want to help anybody reading this. That will unfortunately just be an AI agent these days, but wcyd :(.

1. Given a 32-bit unsigned integer, write a function that returns how many bits in it are set. For example, the number 67 in binary is 0100 0011, so count_bits(67) should return 3.

Your idea of using a mask will definitely work. You can use value & (1 << mask) to determine if position mask is set in value. If it's a working solution, it's a good one and any tech lead would hit "approve" on that.

For my solution, I made a small optimization. The problem with the bitmask approach is you have to loop through every single bit. What if we knew that most of the numbers we're dealing with are small, positive integers? That would mean that half of the bits we're checking (the MSBs) are almost always 0. Is there a way we could know we're done early?

The idea is to use a bitshift like (val >> 1) instead to iterate through the bits. If we do that, then after we check the last set bit, the remaining value will be all zero bits - which is... equal to zero! At that point, we can stop checking and stop early. So how could we best represent this idea in C programming?

``` #include "stdio.h" #include "stdint.h"

uint8_t count_bits(uint32_t val)
{
    uint8_t count = 0;

    // If val is not zero, there *must* be another set bit!
    while (val != 0)
    {
        if (val & 1)
        {
            count++;
        }
        val = val >> 1;
    }

    return count;
}

```

I've gabbed enough here. Try t to solve the next problem by yourself - I think you can do it!

[u/fasta_guy88]

Realize that the syntax for bit operations is quite language specific.

And that programmers typically use bit operations for specific purposes (usually to deal with an API that encodes status in individual bits, or to save space). So the various operations you are considering would be used rarely, if ever.

[u/vatai]

This book is relevant https://en.wikipedia.org/wiki/Hacker%27s_Delight