Ask coding questions

← Back to all posts
How to get a bit from a number, and set it into another number
xxpertHacker (931)

I'm trying to make a function that accepts two unsigned integers by values (a, b), then sets the (N)th bit in (a) to the value of the (N)th bit in (b).

I ended up with this pseudo-code:

N = 1

f(a, b) {
	sign = (b >> N) & 1

	return a | sign
}

My attempt is wrong. I've been looking around at bit-twiddling articles, blog posts, and SO posts, but still don't see why it's wrong.

Does anyone know how to fix it?

I'm thinking that it should be a | sign << N to get the bit into position, but that didn't work.

Answered by 19wintersp (1142) [earned 5 cycles]
View Answer
Comments
hotnewtop
xxpertHacker (931)

@19wintersp Do you know a think or two about bit mutation? Could you help me out?

19wintersp (1142)

@xxpertHacker I don't know how to do this efficiently, but I know you could do it if you know the size of the value. For example, here it is with two u8's, setting the last bit:

fn send_bit(a: u8, b: u8) -> u8 {
  let mask: u8 = 0b00000001 & b;
  a | mask
}

That for the nth bit is:

fn send_bit(a: u8, b: u8, n: u8) -> u8 {
  assert!(n < 8); // n starts at 0

  let mask: u8 = 2.pow(n) & b;
  a | mask
}

And it should work like this:

send_bit(0b10101010, 0b01010101, 3) // 0b10101110

This code isn't tested, and probably doesn't work

19wintersp (1142)

I've just realised this is effectively the same as

a | ((0b1 << n) & b)
xxpertHacker (931)

@19wintersp Oh, mask & sign vs my current sign << n, I'll try it later.

xxpertHacker (931)

@19wintersp Wait no, that makes no sense, v & 1 can only be 0 or 1, so 0b000100 & 1 will just be 0, while 0b0001 & 1 will be 1, thus the mask is wrong.

19wintersp (1142)

@xxpertHacker That's what should happen, isn't it?

As an example, for getting the third bit:

  1. mask becomes 0b00000100
  2. mask ANDed with something will extract that bit only
  3. That value ORed with the target will set that bit to 1 if it's not already
19wintersp (1142)

@xxpertHacker I wrote a quick test, and it seems to work properly:

xxpertHacker (931)

@19wintersp This evaluates to a | mask, where mask is 0 or 1, I don't see how that makes sense?

a | 0 is a, a | 1 sets the first bit, right? I want to set the Nth bit though?

xxpertHacker (931)

@19wintersp Hmm... odd, can you link your test?

19wintersp (1142)

@xxpertHacker

fn send_bit(a: u8, b: u8, n: u8) -> u8 {
	assert!(n < 8);
	
	let mask: u8 = (0b1 << n) & b;
	a | mask
}

fn main() {
	let a = 0b10101010u8;
	let b = 0b01010101u8;
	
	println!("a is {}, b is {}", a, b);
	
	for i in 0..8 {
		println!("sending bit {} of a to b, result: {}", i, send_bit(a, b, i));
	}
}
xxpertHacker (931)

@19wintersp Okay, seems like it does work.

If you can try the following:

fn main() {
	const F: f64 = 4.0;

	println!(
		"({:#b})\n({:#b})",
		F.to_bits(),
		(-F).to_bits()
	);
}

On an LE machine, you should get the following:

0100000000010000000000000000000000000000000000000000000000000000
1100000000010000000000000000000000000000000000000000000000000000

Indicating that the left-most bit is the signbit that changed.

I'm trying to target it with the following:

let with_new_bit: u64 = send_bit(
	float_a.to_bits(),
	float_b.to_bits(),
	63 // last bit, counting from right -> left
);

f64::from_bits(with_new_bit)

any guess as to why this isn't working?

19wintersp (1142)

@xxpertHacker Literally no clue, since it works for me:

fn send_bit(a: u64, b: u64, n: u8) -> u64 {
	assert!(n < 64);

	a | ((0b1 << n) & b)
}

fn main() {
	let my_f64 = 123f64;
	let negative = -456f64;

	let new_f64 = f64::from_bits(
		send_bit(
			my_f64.to_bits(),
			negative.to_bits(),
			63
		)
	);

	println!("{} -> {}", my_f64, new_f64);
}

Output:

123 -> -123
xxpertHacker (931)

@19wintersp Oh, I see the problem, if you have a negative and then a positive, it breaks: (-4.0, 4.0) = -4.0.

This is because 1 | 0 = 1, it doesn't set it if the second bit is 0. Maybe OR isn't the right operation?

19wintersp (1142)

@xxpertHacker No, it's because it's copying a bit from one thing to the other, it's directional, and so the argument order matters.

xxpertHacker (931)

@19wintersp I'm not understanding how it's directional, can you elaborate on why the (-4.0, 4.0) results in (-4.0), if the bit was copied from the rhs' into the lhs?

19wintersp (1142)

@xxpertHacker Apologies, I misread the comment: you're right, it should be something else. Whilst this function is directional, what I made is a broken implementation. Once again, I don't know how to do this well, but something like this might work (for a u8):

let mask: u8 = 0b1 << n;
(~mask | (mask & b)) & a

Edit: no, it doesn't, but this should:

let mask: u8 = 0b1 << n;
(a & ~mask) | (mask & b)
xxpertHacker (931)

@19wintersp Worked flawlessly. The pattern seems familiar and can probably be optimized but the mask will be constant, so it'll be good anyways. Thank you.

Coder100 (18869)

well, apparently rust doesn't like constant ternaries???

maybe make bit position a function instead

xxpertHacker (931)

@Coder100 No, the code works fine on an up-to-date Rustc, but the pseudo-code is wrong, so it fails at runtime.

Try https://play.rust-lang.org, to see it yourself.

But the Rust is just an implementation detail and use, the pseudo-code example is all of the bitwise operations that matter.

Baconman321 (1103)

It just looks like the if statements are throwing syntax errors so I can't really see the problem...

Can you convert the number to a string of bits and perform math that way (AKA: 5 to 101 and replace the last 1 with a bit from another number)?

xxpertHacker (931)

@Baconman321

Can you convert the number to a string of bits and perform math that way (AKA: 5 to 101 and replace the last 1 with a bit from another number)?

No strings, that is not math.

Baconman321 (1103)

@xxpertHacker You never said in your post that it had to be with only math :/

xxpertHacker (931)

@Baconman321 You cannot perform "math" on strings, I don't know what programmer or mathematician would say that you can.

I'm writing branchless code that operates on bits to emulate missing hardware instructions, but I'm told that I should go heap allocate two strings, change a character, parse the string into a number, free the strings, etc.

Like, wtf? That is how poorly performing garbage software is made. I don't need to be micro-optimizing in order to see that.

Baconman321 (1103)

@xxpertHacker ok, well with the little details that I had from your post it was hard to see...

Oh, I see... my term "math" confused you (or not IDK).

Sorry... I meant to perform shifting and such using strings. Yes, I can see how that is slow.

It was merely a suggestion. Sometimes we are so focused on one problem that we don't see the solution because it is from another angle. And sometimes, looking at it from a different angle won't work as well...

If it doesn't work then it doesn't work...

xxpertHacker (931)

@Baconman321 It would work, as it, technically the result would be accurate, but I usually have a performance baseline goal, and in this case, equivalent code could look like the following:

f(a, b) {
    if b > 0 {
        return a
    } else {
        return -a
   }
}
Baconman321 (1103)

@xxpertHacker Ok, I'll try to find out how to use bitwise manipulation in this case.