Shift an array to the right with 1

Question

I'm trying to shift an array of unsigned char to the right with some binary 1.

Example: 0000 0000 | 0000 1111 that I shift 8 times will give me 0000 1111 | 1111 1111 (left shift in binary)

So in my array I will get: {0x0F, 0x00, 0x00, 0x00} => {0xFF, 0x0F, 0x00, 0x00} (right shift in the array)

I currently have this using the function memmove:

unsigned char * dataBuffer = {0x0F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};

unsigned int shift = 4;
unsigned length = 8;

memmove(dataBuffer, dataBuffer - shift, length + shift);    
for(int i = 0 ; i < 8 ; i++) printf("0x%X ", dataBuffer[i]);

Output: 0x0 0x0 0x0 0x0 0xF 0x0 0x0 0x0
Expected output: 0xFF 0x0 0x0 0x0 0x0 0x0 0x0 0x0

As you can see, I managed to shift my array only element by element and I don't know how to replace the 0 with 1. I guess that using memset could work but I can't use it correctly.

Thanks for your help!

EDIT: It's in order to fill a bitmap zone of an exFAT disk. When you write a cluster in a disk, you have to set the corresponding bit of the bitmap to 1 (first cluster is first bit, second cluster is second bit, ...).

A newly formatted drive will contain 0x0F in the first byte of the bitmap so the proposed example corresponds to my needs if I write 8 clusters, I'll need to shift the value 8 times and fill it with 1.

In the code, I write 4 cluster and need to shift the value by 4 bits but it is shifted by 4 bytes.

Setting the question as solved, it isn't possible to do what I want. Instead of shifting the bits of an array, I need to shift each byte of the array separately.

For these kind of questions it is better to clearly state the problem. What do they look like - input and output? What is expected behaviour exactly? You gave one example, but is that really covering your requirement? What do you need that for? — Ely, Jun 16 '16 at 14:16
It's in order to fill a bitmap zone of an exFAT disk. When you write a cluster in a disk, you have to set the corresponding bit of the bitmap to 1 (first cluster is first bit, second cluster is second bit, ...). A newly formatted drive will contain 0x0F in the first byte of the bitmap so the proposed example corresponds to my needs if I write 8 clusters, I'll need to shift the value 8 times and fill it with 1. — Arthur Penguin, Jun 16 '16 at 14:24
Shifting doesn't make sense here - first, you are selecting which clusters are written, which doesn't involve shifting at all, just set the bits that correspond to the clusters that you are writing (they may not be contiguous anyway). second, your examples show that you are shifting to the right but padding with 1's rather than 0's, which is the opposite of normal bit-shifting. To bit-shift, you use the << and >> bit-level operators to do it, managing overflow yourself for whatever word size you use to shift. However, based on your description, that doesn't sound like what you really want. — Matt Jordan, Jun 16 '16 at 14:36
@ArthurPenguin Can you please first check if the following link answers your question? http://stackoverflow.com/a/47990/1566187 — Ely, Jun 16 '16 at 14:37
Possible duplicate of [How do you set, clear and toggle a single bit in C/C++?](http://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit-in-c-c) — Ely, Jun 16 '16 at 14:39
- The application I'm writing involves sequential files which means that the cluster I want to write are contiguous. When I want to write a file of X clusters, I want to shift the value by X with 1 padding, which is easier than: read the last written byte of the bitmap (0x03 for example), write 0xFF (6 bits more), fill the (X - 6 - Y) next bytes with 0xFF with Y the remainder of (X - 6) / 8 and write the corresponding value to Y in the last byte. - I tried << and >> operators but it doesn't work for array of char, so if you have an alternative for this, I'd be glad to know. — Arthur Penguin, Jun 16 '16 at 16:11
Do you need to shift the entire array by 4 bits or a single byte by 4 bits? — Thomas Matthews, Jun 16 '16 at 16:23
This task may be easier in assembly language. Many processors have rotate and shift instructions that are not available in C++. — Thomas Matthews, Jun 16 '16 at 16:24
Yeah it would be the entire array since I could have to shift more than one byte at once. Guess it's not possible? I will have to do it byte per byte then. — Arthur Penguin, Jun 16 '16 at 16:28

Arthur Penguin · Accepted Answer · 2016-06-17T13:45:35.763

Setting the question as solved, it isn't possible to do what I want. Instead of shifting the bits of an array, I need to edit each bit of the array separately.

Here's the code if it can help anyone else:

unsigned char dataBuffer[11] = {0x0F, 0x00, 0x00, 0x00, 0, 0, 0, 0};
unsigned int sizeCluster = 6;
unsigned int firstCluster = 4;
unsigned int bitIndex = firstCluster % 8;
unsigned int byteIndex = firstCluster / 8;
for(int i = 0 ; i < sizeCluster; i++){
    dataBuffer[byteIndex] |= 1 << bitIndex;
    //printf("%d ", bitIndex);
    //printf("%d \n\r", byteIndex);
    bitIndex++;
    if(bitIndex % 8 == 0){
        bitIndex = 0;
        byteIndex++;
    }
}
for(int i = 0 ; i < 10 ; i++) printf("0x%X ", dataBuffer[i]);

OUTPUT: 0xFF 0x3 0x0 0x0 0x0 0x0 0x0 0x0 0x0 0x0

sizeCluster is the number of clusters I want to add in the Bitmap firstCluster is the first cluster where I can write my data (4 clusters are used: 0, 1, 2, and 3 so I start at 4). bitIndex is used to modify the right bit in the byte of the array => increments each time. byteIndex is used to modify the right byte of the array => increments each time the bit is equal to 7.

you are not shifting the array, you are just setting particular bits for particular cluster, this is classic bit-mask set. Question is, why you don't use C++ [bitset](http://www.cplusplus.com/reference/bitset/bitset/) — Ped7g, Jun 17 '16 at 13:35
Most of the time (always in fact) I manipulate the array as byte, not as bit. It is only required for the bitmap in my conception so I have never considered converting it in bits (I was using FAT32 until now). Didn't know the bitset function, do you think it would be more optimized? The sata function that I use to read/write data uses an unsigned char buffer so I would need to convert them back into bytes. — Arthur Penguin, Jun 17 '16 at 13:51

Ped7g · Answer 2 · 2016-06-17T15:05:22.360

In case you don't want to use C++ std::bitset for performance reasons, then your code can be rewrote like this:

#include <cstdio>
#include <cstdint>

    // buffer definition
    constexpr size_t clustersTotal = 83;
    constexpr size_t clustersTotalBytes = (clustersTotal+7)>>3; //ceiling(n/8)
    uint8_t clustersSet[clustersTotalBytes] = {0x07, 0};
        // clusters 0,1 and 2 are already set (for show of)

    // helper constanst bit masks for faster bit setting
    // could be extended to uint64_t and array of qwords on 64b architectures
    // but I couldn't be bothered to write all masks by hand.
    // also I wonder when the these lookup tables would be large enough
    // to disturb cache locality, so shifting in code would be faster.
    const uint8_t bitmaskStarting[8] = {0xFF, 0xFE, 0xFC, 0xF8, 0xF0, 0xE0, 0xC0, 0x80};
    const uint8_t bitmaskEnding[8] = {0x01, 0x03, 0x07, 0x0F, 0x1F, 0x3F, 0x7F, 0xFF};
    constexpr uint8_t bitmaskFull = 0xFF;

    // Input values
    size_t firstCluster = 6;
    size_t sizeCluster = 16;

    // set bits (like "void setBits(size_t firstIndex, size_t count);" )
    auto lastCluster = firstCluster + sizeCluster - 1;
    printf("From cluster %d, size %d => last cluster is %d\n",
           firstCluster, sizeCluster, lastCluster);
    if (0 == sizeCluster || clustersTotal <= lastCluster)
        return 1;     // Invalid input values
    auto firstClusterByte = firstCluster>>3; // div 8
    auto firstClusterBit = firstCluster&7;   // remainder
    auto lastClusterByte = lastCluster>>3;
    auto lastClusterBit = lastCluster&7;
    if (firstClusterByte < lastClusterByte) {
        // Set the first byte of sequence (by mask from lookup table (LUT))
        clustersSet[firstClusterByte] |= bitmaskStarting[firstClusterBit];
        // Set bytes between first and last (simple 0xFF - all bits set)
        while (++firstClusterByte < lastClusterByte)
            clustersSet[firstClusterByte] = bitmaskFull;
        // Set the last byte of sequence (by mask from ending LUT)
        clustersSet[lastClusterByte] |= bitmaskEnding[lastClusterBit];
    } else {    //firstClusterByte == lastClusterByte special case
        // Intersection of starting/ending LUT masks is set
        clustersSet[firstClusterByte] |=
            bitmaskStarting[firstClusterBit] & bitmaskEnding[lastClusterBit];
    }

    for(auto i = 0 ; i < clustersTotalBytes; ++i)
        printf("0x%X ", clustersSet[i]); // Your debug display of buffer

Unfortunately I didn't profile any of the versions (yours vs my), so I have no idea what is the quality of optimized C compiler output in both cases. In the ages of lame C compilers and 386-586 processors my version would be much faster. With modern C compiler the LUT usage can be a bit counterproductive, but unless somebody proves me wrong by some profiling results, I still think my version is much more efficient.

That said, as writing to file system is probably involved ahead of this, setting bits will probably take about %0.1 of CPU time even with your variant, I/O waiting will be major factor.

So I'm posting this more like an example how things can be done in different way.

Edit:

Also if you believe in the clib optimization, the:

        // Set bytes between first and last (simple 0xFF - all bits set)
        while (++firstClusterByte < lastClusterByte)
            clustersSet[firstClusterByte] = bitmaskFull;

Can reuse clib memset magic:

//#include <cstring>
    // Set bytes between first and last (simple 0xFF - all bits set)
    if (++firstClusterByte < lastClusterByte)
        memset(clustersSet, bitmaskFull, (lastClusterByte - firstClusterByte));

Shift an array to the right with 1

2 Answers2