"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[i] = 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[i] & (1<<j))>>j)<<(i/modgroup));
}
}

for(int i = 0; i < arraysize; i++)
cout << seed[i] << " " << array[i] << 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[i] & (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]

Re: &quot;Bitslicin g&quot;

"J. Campbell" wrote:[color=blue]
>
> 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[/color]

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

/david

--
Andre, a simple peasant, had only one thing on his mind as he crept
along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
-- unknown

[Thomas Matthews]

Re: &quot;Bitslicin g&quot;

J. Campbell wrote:
[color=blue]
> David Rubin <bogus_address@ nomail.com> wrote in message news:<3F3A3E9D. 8E3634D7@nomail .com>...
>[color=green]
>>"J. Campbell" wrote:
>>[color=darkred]
>>>I'm tring to turn an array on it's ear...bitwise. What I want to do
>>>is the following...[/color][/color]
>
>[color=green]
>>It sounds like you want to transpose each contiguous 4x4 submatrix.
>>/david[/color]
>
>
> 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.[/color]

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.l earn.c-c++ faq:

http://www.raos.demon.uk/acllc-c++/faq.html

Other sites:
http://www.josuttis.com -- C++ STL Library book