How to set the 513th bit of a char[1024] in C?

Question

I was recently asked in an interview how to set the 513th bit of a char[1024] in C, but I'm unsure how to approach the problem. I saw How do you set, clear, and toggle a single bit?, but how do I choose the bit from such a large array?

Answer 1

int bitToSet = 513;
inArray[bitToSet / 8] |= (1 << (bitToSet % 8));

...making certain assumptions about character size and desired endianness.

EDIT: Okay, fine. You can replace 8 with CHAR_BIT if you want.

Answer 2

#include <limits.h>

int charContaining513thBit = 513 / CHAR_BIT;
int offsetOf513thBitInChar = 513 - charContaining513thBit*CHAR_BIT;

int bit513 = array[charContaining513thBit] >> offsetOf513thBitInChar & 1;

Answer 3

You have to know the width of characters (in bits) on your machine. For pretty much everyone, that's 8. You can use the constant CHAR_BIT from limits.h in a C program. You can then do some fairly simple math to find the offset of the bit (depending on how you count them).

Numbering bits from the left, with the 2⁷ bit in a[0] being bit 0, the 2⁰ bit being bit 7, and the 2⁷ bit in a[1] being bit 8, this gives:

offset = 513 / CHAR_BIT;  /* using integer (truncating) math, of course */
bit = 513 % CHAR_BIT;
a[offset] |= (0x80>>bit)

There are many sane ways to number bits, here are two:

 a[0]                      a[1]
 0  1  2  3  4  5  6  7     8  9 10 11 12 13 14 15     This is the above
 7  6  5  4  3  2  1  0    15 14 13 12 11 10  9  8     This is |= (1<<bit)

You could also number from the other end of the array (treating it as one very large big-endian number).

Answer 4

Small optimization:

The / and % operators are rather slow, even on a lot of modern cpus, with modulus being slightly slower. I would replace them with the equivalent operations using bit shifting (and subtraction), which only works nicely when the second operand is a power of two, obviously.

x / 8 becomes x >> 3
x % 8 becomes x-((x>>3)<<3)
for this second operation, just reuse the result from the initial division.

Answer 5

Depending on the desired order (left to right versus right to left), it might change. But the general idea assuming 8 bits per byte would be to choose the byte as. This is expanded into lots of lines of code to hopefully show more clearly the intended steps (or perhaps it just obfuscates the intention):

int bitNum = 513;
int bytePos = bitNum / 8;  

Then the bit position would be computed as:

int bitInByte = bitNum % 8;

Then set the bit (assuming the goal is to set it to 1 as opposed to clear or toggle it):

charArray[bytePos] |= ( 1 << bitInByte );

Answer 6

When you say 513th are you using index 0 or 1 for the 1st bit? If it's the former your post refers to the bit at index 512. I think the question is valid since everywhere else in C the first index is always 0.

BTW

static char chr[1024];
...
chr[512>>3]=1<<(512&0x7);