"Bitslicing"

[J. Campbell]

I'm tring to turn an array on it's ear...bitwise. What I want to do
is the following...

suppose I have the following array (each element represents a single
bit)

array1 = {1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

I view it as follows:

array[0] = 1111
array[1] = 0000
array[2] = 0000
array[3] = 0000


I want to transform it to array2 so that I get
array2[0] = 1000
array2[1] = 1000
array2[2] = 1000
array2[3] = 1000


I've written the following code that does what I want:

(code follows)
_____
#include <iostream>

using namespace std;

int main(){

unsigned int arraysize = 32;
unsigned long array[32] = {};
unsigned int seedsize = 32;
unsigned long seed[32] = {};

/*
for(int i = 0; i < seedsize ; i++)
seed = 1;
*/

seed[0] = 0xffffffff;

int bits_per_word = 8 * sizeof(unsigned long);
unsigned int modgroup = arraysize / bits_per_word;

unsigned long ifactor;

for(int i = 0; i < seedsize; i++){
ifactor = (bits_per_word * (i % modgroup));
for(unsigned long j = 0; j < bits_per_word; j++){
array[ifactor+j] |= (((seed & (1<<j))>>j)<<(i/modgroup));
}
}

for(int i = 0; i < arraysize; i++)
cout << seed << " " << array << endl;
cout << endl;
}

____
end code

This works fine. However I'm wondering if there is a beter way to do
this line:
array[ifactor + j] |= (((seed & (1 << j)) >> j) << (i/modgroup));
?

Any suggestions?

It seems like there's got to be an easier way than doing 3 shift
operations...

Thanks in advance for any help you can offer.

 

[David Rubin]

I'm tring to turn an array on it's ear...bitwise. What I want to do
is the following...

suppose I have the following array (each element represents a single
bit)

array1 = {1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}

I view it as follows:

array[0] = 1111
array[1] = 0000
array[2] = 0000
array[3] = 0000

I want to transform it to array2 so that I get
array2[0] = 1000
array2[1] = 1000
array2[2] = 1000
array2[3] = 1000

It sounds like you want to transpose each contiguous 4x4 submatrix. This
is pretty straightforward.

/david

 

[Thomas Matthews]

It sounds like you want to transpose each contiguous 4x4 submatrix.
/david

Actually, I want to transpose the bits on a 1024 element array of
32-bit words, as such:

bit 1 of OldArray[0] --> bit 1 of NewArray[0]
bit 2 of OldArray[0] --> bit 1 of NewArray[1]
bit 3 of OldArray[0] --> bit 1 of NewArray[2]
.
.
bit 1 of OldArray[1] --> bit 1 of NewArray[32]
bit 2 of OldArray[1] --> bit 1 of NewArray[33]
.
.
bit 1 of OldArray[32] --> bit 2 of NewArray[0]
bit 2 of OldArray[32] --> bit 2 of NewArray[1]
.
.
bit 1 of OldArray[992] --> bit 32 of NewArray[0]
bit 2 of OldArray[992] --> bit 32 of NewArray[1]
.
.
bit 1 of OldArray[1023]--> bit 32 of NewArray[992]
bit 2 of OldArray[1023]--> bit 32 of NewArray[993]
.
.
bit 32 of OldArray[1023]--> bit 32 of NewArray[1023]

I've written code to do this (shown in the original post), and was
wondering if anyone had a more elegant way to do this.

Thanks.

You may find using assembly language to be more efficient, if it has
instructions that are more efficient.

Otherwise, treat it as a matrix of unsigned integers. Convert from
bits into unsigned integers of one or zero. Perform the translation,
then convert back.


--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book