Setting last N bits in an array

Question

I'm sure this is fairly simple, however I have a major mental block on it, so I need a little help here!

I have an array of 5 integers, the array is already filled with some data. I want to set the last N bits of the array to be random noise.

[int][int][int][int][int]

eg. set last 40 bits

[unchanged][unchanged][unchanged][24 bits of old data followed 8 bits of randomness][all random]

This is largely language agnostic, but I'm working in C# so bonus points for answers in C#

First you have to define the order of bits in an int, whether MSB or LSB comes first. — starblue, Apr 22 '10 at 05:29
Whatever the native system order is. Ie, it might be different on different machines and I want to be able to handle that — Martin, Apr 29 '10 at 09:28

score 3 · Accepted Answer · answered Apr 21 '10 at 23:33

3

Without any bit-fu in C#:

BitArray ba = new BitArray (originalIntArray);
for (int i = startToReplaceFrom; i < endToReplaceTo; i++)
    ba.Set (i, randomValue);

answered Apr 21 '10 at 23:33

Foxfire

5,675
21
29

Ah, a bit array, of course! I was all up to my neck in bit foo and didn't think of the obvious – Martin Apr 21 '10 at 23:51

Mark Byers · Answer 2 · 2010-04-21T23:28:47.380

1

When you XOR any data with random data, the result is random, so you can do this:

Random random = new Random();
x[x.Length - 2] ^= random.Next(1 << 8);
x[x.Length - 1] = random.Next(1 << 16);
x[x.Length - 1] ^= random.Next(1 << 16) << 16;

For a general solution for any N you can use a loop:

for (int i = 0; i < 40; ++i)
{
    x[x.Length - i / 32 - 1] ^= random.Next(2) << (i % 32);
}

Note that this calls random more times than necessary, but is simple.

edited Apr 21 '10 at 23:28

answered Apr 21 '10 at 23:23

Mark Byers

811,555
193
1,581
1,452

This is only a solution for the specific example I gave above,not the general case? Besides that, I don't quite understand what you're doing in the last case, why the two sets of randomness for the last index? – Martin Apr 21 '10 at 23:27
@Martin: First set the lower 16 bits, then set the upper 16 bits. – Mark Byers Apr 21 '10 at 23:45
Ah, because if you just used the 32 bits from random the msb would never be set thanks to 2s complement? – Martin Apr 21 '10 at 23:47
@Martin: Yes, if you use random.Next() you can get only 31 random bits because it guarantees only positive values. – Mark Byers Apr 21 '10 at 23:50

score 0 · Answer 3 · answered Apr 21 '10 at 23:26

0

In pseudo-Python:

N        = 5   # array size
bits     = 40  # for instance
int_bits = 32  # bits in one integer

i = N
while bits > 0:
    value_bits  = min (bits, int_bits)
    bits       -= value_bits
    mask        = (1 << value_bits) - 1

    i -= 1
    array[i] ^= random () & mask

answered Apr 21 '10 at 23:26

@Martin: To think, this depends on machine endiness. What exactly do you mean by last bits? – Apr 21 '10 at 23:33

score 0 · Answer 4 · answered Apr 21 '10 at 23:40

Int32 is 4 bytes or 32 bits.
So you need the last int, and 8 bits extra.

int lastEightBitsMask = 0x000F + 1;
Random rand = new Random();
arr[arr.Length - 1] = rand.Next();
arr[arr.Length - 2] ^= rand.Next(lastEightBitsMask);

Explanation:
The last element's modification should be pretty clear - if you need the last 40 bits, the last 32 bits are included in that.
The remaining eight bits's modification is bounded above by 0x000F + 1, since rand.Next's argument is an exclusive upper bound, the randoms generated will be no more than that. The remaining bits of the number will stay the same, since 1^0 == 1 and 0^0 == 0.

Setting last N bits in an array

4 Answers4