Back to General and Gameplay Programming

Hwo to read bit and set same bit in different byte

General and Gameplay Programming Programming

Started by Misery October 16, 2012 11:52 AM

21 comments, last by Misery 11 years, 6 months ago

Misery

354

Author

October 16, 2012 11:52 AM

Hello,

I am using integers as bit containers representing bool values.
How do I make a fast instruction that reads some bit from one integer and sets its value to another.
Lets say: there are two 64 bit integers. One of them x has some bits set.
I want to rewrite every second bit from x to y (from beginning). How do I make that avoiding code similar to that:



y=0; //clear y

t=0;

for (int i=0;i<64;i+=2)

	if (x & (CONTAINER_INT(1) << (i%ContainerSize)))

   {

	  y |= CONTAINER_INT(1) << (t%ContainerSize);

	 t++;

   }

I mean I want to avoid if instruction.

Regards.

alh420

5,995

October 16, 2012 12:10 PM

something like this?

y |= x&0x5555555555555555LL;

Misery

354

Author

October 16, 2012 12:17 PM

@Olof Hedman: No. I need to rewrite them bit by bit.

alh420

5,995

October 16, 2012 12:25 PM

why? I assume you also do something else then, besides the copying of every second bit?

If you need to do it bit by bit, I don't think you have any choice but to check it bit by bit.

My code copies all of them from x at the same time, not caring what they are, and conserve all of the other bits from y

Edit: this if you also need to copy zeros

y = (y&0xAAAAAAAAAAAAAAAALL) | (x&0x5555555555555555LL);

Brother Bob

10,350

October 16, 2012 12:35 PM

why? I assume you also do something else then, besides the copying of every second bit?

If you need to do it bit by bit, I don't think you have any choice but to check it bit by bit.

My code copies all of them from x at the same time, not caring what they are, and conserve all of the other bits from y

Your code doesn't match his. The bit index for the source and the destination are different variables; the source bit index is the loop index i, but the destination index is t which is stepped by one and only stepped for on-bits inside the if-statement. The behavior of his code is effectively: count the number of on-bits in every second bit index, and set that many bits in the destination. If the source contains 5 on-bits when counting every second bit, then the first 5 bits in the destination is set.

Although I'd say that his code and description doesn't convey the same message, and neither are very clear. A full description of the actual problem will help a lot.

alh420

5,995

October 16, 2012 12:42 PM

Your code doesn't match his. The bit index for the source and the destination are different variables; the source bit index is the loop index i, but the destination index is t which is stepped by one and only stepped for on-bits inside the if-statement. The behavior of his code is effectively: count the number of on-bits in every second bit index, and set that many bits in the destination. If the source contains 5 on-bits when counting every second bit, then the first 5 bits in the destination is set.

Although I'd say that his code and description doesn't convey the same message, and neither are very clear. A full description of the actual problem will help a lot.

Ah right. I actually assumed the t inside the if was a typo, since putting it outside in the for loop matches the description in the post and title

Brother Bob

10,350

October 16, 2012 01:01 PM

[quote name='Brother Bob' timestamp='1350390907' post='4990694']
Your code doesn't match his. The bit index for the source and the destination are different variables; the source bit index is the loop index i, but the destination index is t which is stepped by one and only stepped for on-bits inside the if-statement. The behavior of his code is effectively: count the number of on-bits in every second bit index, and set that many bits in the destination. If the source contains 5 on-bits when counting every second bit, then the first 5 bits in the destination is set.

Although I'd say that his code and description doesn't convey the same message, and neither are very clear. A full description of the actual problem will help a lot.

Ah right. I actually assumed the t inside the if was a typo, since putting it outside in the for loop matches the description in the post and title
[/quote]
Actually, putting t++ in the loop itself makes yet another interpretation of the problem: it copies bit index 2*n to bit index n, since i increases by two and t increases by one each loop in that case.

The exact details here are important and, as I said, we need to know the actual problem. So far we've had two different descriptions, and yet another interpretation of it

alvaro

21,604

October 16, 2012 03:21 PM

y=0; //clear y t=0; for (int i=0;i<64;i+=2) if (x & (CONTAINER_INT(1) << (i%ContainerSize))) { y |= CONTAINER_INT(1) << (t%ContainerSize); t++; }

y = (CONTAINER_INT(1)<<popcount(x & 0x555555555555555ul)) - 1;

EDIT: popcount stands for "population count", which means count the number of bits set. gcc provides __builtin_popcount for you, or you can use one of the tricks described in Bit Twiddling Hacks. Oh, and I am not sure why you are doing `%ContainerSize'.

Misery

354

Author

October 16, 2012 06:02 PM

OK, so little more explanation:
I have a bitset matrix (B) and two indexing integer matrices (i,j).
What I want is to create another bitset matrix that consists of B entries at the indexes defined by i and j.
It is a similar behavior like that in Matlab or Scilab.

So what I need is to rewrite B(i,j) to new bitset matrix. B entries can be 1 or 0 so I need to rewrite them bit by bit, as new matrix can have different size from B.

To complicate even more used integer depend on the platform and may have 16 32 or 64 bits. This is dependent on the template parameter CONTAINER_INT.

alvaro

21,604

October 16, 2012 06:06 PM

So your question has nothing to do with the code in your first post.

If I understand your problem correctly, I don't think you can do better than bit by bit.

Hwo to read bit and set same bit in different byte

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Hwo to read bit and set same bit in different byte

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines