There is byte[]

It is required to perform for it a bit shift to the left or to the right with minimal cost.

While searching for solutions, I stumbled upon BitArray . One of its constructors takes an array of bytes. The class allows you to perform various bit operations (AND NOT OR XOR), but does not allow for shifts.

  • 2
    And the variant with a shift of each byte separately in the cycle you do not consider to be an option with minimal cost? - Regent
  • stackoverflow.com/questions/8440938/… - Alex78191
  • 2
    @Regent, his mention implies that he wants to move the array of bits entirely, and not lose one bit from each byte, doesn’t it? - Qwertiy ♦
  • one
    @iRumba so you need to move each byte separately? - Alex78191
  • 2
    @iRumba in my opinion, you all confused my comment about my version. I just talked about the option in which a shift occurs in each byte, regardless of the results of shifting other bytes. That is exactly what Alex78191 brought in his second answer. And yet, it turns out that you need to make a shift that is dependent on other bytes. - Regent

6 answers 6

Could try

 return ((new System.Numerics.BigInteger(b)) << k).ToByteArray()

although the potential 3 copies of the array are somewhat alarming.

However, you can look at its source and somehow use the appropriate code:

 public static BigInteger operator <<(BigInteger value, int shift) { if (shift == 0) return value; else if (shift == Int32.MinValue) return ((value >> Int32.MaxValue) >> 1); else if (shift < 0) return value >> -shift; int digitShift = shift / kcbitUint; int smallShift = shift - (digitShift * kcbitUint); uint[] xd; int xl; bool negx; negx = GetPartsForBitManipulation(ref value, out xd, out xl); int zl = xl + digitShift + 1; uint[] zd = new uint[zl]; if (smallShift == 0) { for (int i = 0; i < xl; i++) { zd[i + digitShift] = xd[i]; } } else { int carryShift = kcbitUint - smallShift; uint carry = 0; int i; for (i = 0; i < xl; i++) { uint rot = xd[i]; zd[i + digitShift] = rot << smallShift | carry; carry = rot >> carryShift; } zd[i + digitShift] = carry; } return new BigInteger(zd, negx); }
  • What is kcbitUint ? What is the GetPartsForBitManipulation feature? - iRumba
  • kcbitUint - the number of bits, in your case - in a byte, in them - in the inte. GetPartsForBitManipulation - some kind of handling of the shift of negative numbers - you should also be unnecessary. - Qwertiy ♦
  • * ak my brain! I have written my function already. I tested it on 10 ^ 7 iterations. It worked for 500 ms approximately. Now launched BigInteger shift 1 left with the same number of iterations and ... it is still running! It's been over 4 minutes! OO - iRumba
  • Well, that's right. BigInteger during the shift increases the number of bytes. That is, it’s as if I did svdig for an int, but in the end I could get a long one. - iRumba
  • @iRumba, yes, BigInteger is growing) But you can still get the idea from their code. - Qwertiy ♦
 #region сдвиг Π½Π° 1 Π±ΠΈΡ‚ byte[] myBytes; BitArray gamma_value = new BitArray(myBytes); int len = gamma_value.Length; //Π΄Π»ΠΈΠ½Π° массива Π±ΠΈΡ‚ c = gamma_value[0]; //младший Π±ΠΈΡ‚ //созданиС массива Ρ‚ΠΈΠΏΠ° bool //Ρ‚Π°ΠΊΠΎΠΉ ΠΆΠ΅ Π΄Π»ΠΈΠ½Ρ‹ ΠΊΠ°ΠΊ gamma_value Ρ‚ΠΈΠΏΠ° BitArray bool[] gamma_new = new bool[len]; //ΠΊΠΎΠΏΠΈΡ€ΡƒΠ΅ΠΌ массив Ρ‚ΠΈΠΏΠ° BitArray Π² массив Ρ‚ΠΈΠΏΠ° bool gamma_value.CopyTo(gamma_new, 0); //ΠΊΠΎΠΏΠΈΡ€ΡƒΠ΅ΠΌ массив bool со сдвигом Π½Π° 1Π½Ρƒ ΠΏΠΎΠ·ΠΈΡ†ΠΈΡŽ Π² Π΄Ρ€ΡƒΠ³ΠΎΠΉ массив bool Array.Copy(gamma_new, 1, gamma_new, 0, len - 1); //ΠΏΡ€Π΅ΠΎΠ±Ρ€Π°Π·ΠΎΠ²Π°Π½ΠΈΠ΅ массива Ρ‚ΠΈΠΏΠ° bool Π² массив Ρ‚ΠΈΠΏΠ° BitArray gamma_value = new BitArray(gamma_new); gamma_value.CopyTo(myBytes, 0); //ΠΏΠ΅Ρ€Π΅Π²ΠΎΠ΄ΠΈΠΌ массив Π±ΠΈΡ‚ Π² массив Π±Π°ΠΉΡ‚ #endregion
  • one
    Very ineffective, not? - Qwertiy ♦
  • one
    @Qwertiy at least with minimal coding. - Alex78191
  • I need the minimum cost of execution time (for a computer resource) - iRumba
  • @iRumba, try SIMD? - Qwertiy ♦
  • @Qwertiy, can you be specific? - iRumba

The idea is to manually copy the bits. That is, if we shift to the left by 4 bits, then we copy the 4th bit into the 0th bit, the 5th bit into the 1st, and so on. Accordingly, in, for example, the 15th bit (2nd byte) the 19th bit (3rd byte) is copied.

To shift to the right - the same.

 private static readonly byte[] bits = new byte[] { 0x80, 0x40, 0x20, 0x10, 8, 4, 2, 1 }; public static byte[] ShiftLeft(byte[] array, int shift) { var result = new byte[array.Length]; var totalLength = array.Length * 8; for (var toIndex = 0; toIndex < totalLength - shift; toIndex++) { var fromIndex = toIndex + shift; SetBit(fromIndex, toIndex, array, result); } return result; } public static byte[] ShiftRight(byte[] array, int shift) { var result = new byte[array.Length]; var totalLength = array.Length * 8; for (var toIndex = totalLength - 1; toIndex >= shift; toIndex--) { var fromIndex = toIndex - shift; SetBit(fromIndex, toIndex, array, result); } return result; } private static void SetBit(int fromIndex, int toIndex, byte[] fromArray, byte[] toArray) { var fromByte = fromArray[fromIndex / 8]; var fromBit = bits[fromIndex % 8]; if ((fromByte & fromBit) != 0) { toArray[toIndex / 8] |= bits[toIndex % 8]; } }
  • Need for any number - iRumba
  • @iRumba made for any number. In the evening, after work, I will think about simplifying the code. - Regent
  • It spoils the original set. - iRumba
  • @iRumba so you never wrote anywhere that you need a copy of the array. One could have guessed about the shift to any number of bits, but a copy is already a bust. Again, you have to change the code. - Regent
  • I did not think it was necessary to speak. The implication was that the function should work the same way as for ordinary numbers (of type int or long). The fact is that various bitwise operations are rarely used in a single instance. Typically, this is a set of operations, like A << 1 | A >> x - 1 A << 1 | A >> x - 1 (ROL 1). Your implementation will spoil life to the programmer who will use it. - iRumba

The shift will have to be implemented algorithmically: it is required, based on the amount of shift in the cycle, to determine in which byte the data from the current byte will fall. Byte data is divided into two parts: the displaced and the displaced part.

The task is easy to solve, but it takes time. I advise you to split the task into several parts, for example: turn any negative bias into a positive one; make the transition to all bytes in the loop; split the byte into two parts - the one that fell after the offset and the second; in local variables to write the values ​​of the new indices and offsets in their bytes for the data of the current byte; write to another array of the same length by offset indices

  • I'll think about it. How to get to the studio. Otherwise it’s hard to imagine the code in the head and how it will be executed - iRumba
 /// <summary> /// Rotates the bits in an array of bytes to the left. /// </summary> /// <param name="bytes">The byte array to rotate.</param> public static void RotateLeft(byte[] bytes) { bool carryFlag = ShiftLeft(bytes); if (carryFlag == true) { bytes[bytes.Length - 1] = (byte)(bytes[bytes.Length - 1] | 0x01); } } /// <summary> /// Rotates the bits in an array of bytes to the right. /// </summary> /// <param name="bytes">The byte array to rotate.</param> public static void RotateRight(byte[] bytes) { bool carryFlag = ShiftRight(bytes); if (carryFlag == true) { bytes[0] = (byte)(bytes[0] | 0x80); } } /// <summary> /// Shifts the bits in an array of bytes to the left. /// </summary> /// <param name="bytes">The byte array to shift.</param> public static bool ShiftLeft(byte[] bytes) { bool leftMostCarryFlag = false; // Iterate through the elements of the array from left to right. for (int index = 0; index < bytes.Length; index++) { // If the leftmost bit of the current byte is 1 then we have a carry. bool carryFlag = (bytes[index] & 0x80) > 0; if (index > 0) { if (carryFlag == true) { // Apply the carry to the rightmost bit of the current bytes neighbor to the left. bytes[index - 1] = (byte)(bytes[index - 1] | 0x01); } } else { leftMostCarryFlag = carryFlag; } bytes[index] = (byte)(bytes[index] << 1); } return leftMostCarryFlag; } /// <summary> /// Shifts the bits in an array of bytes to the right. /// </summary> /// <param name="bytes">The byte array to shift.</param> public static bool ShiftRight(byte[] bytes) { bool rightMostCarryFlag = false; int rightEnd = bytes.Length - 1; // Iterate through the elements of the array right to left. for (int index = rightEnd; index >= 0; index--) { // If the rightmost bit of the current byte is 1 then we have a carry. bool carryFlag = (bytes[index] & 0x01) > 0; if (index < rightEnd) { if (carryFlag == true) { // Apply the carry to the leftmost bit of the current bytes neighbor to the right. bytes[index + 1] = (byte)(bytes[index + 1] | 0x80); } } else { rightMostCarryFlag = carryFlag; } bytes[index] = (byte)(bytes[index] >> 1); } return rightMostCarryFlag; }

As a result, I got 2 functions:

Shift left

 public static byte[] ShiftLeft(byte[] src, int val) { var res = new byte[src.Length]; var byteShift = val >> 3; if (byteShift >= src.Length) return res; val ^= byteShift << 3; for (var i = 1; i < src.Length - byteShift; i++) res[i + byteShift] = (byte)((src[i] << val) | src[i - 1] >> 8 - val); res[byteShift] = (byte)(src[0] << val); return res; }

And right shift

 public static byte[] ShiftRight(byte[] src, int val) { var res = new byte[src.Length]; var byteShift = val >> 3; if (byteShift >= src.Length) return res; val ^= byteShift << 3; for (var i = byteShift; i < src.Length - 1; i++) res[i - byteShift] = (byte)((src[i] >> val) | src[i + 1] << 8 - val); res[src.Length - byteShift - 1] = (byte)(src[src.Length - 1] >> val); return res; }

Functions "as is" suggest proper use. Speed ​​is very important to me, so I did not check for negative values. Ideally, a negative left shift is a right shift by the same number modulo.

It was also possible to add checks for zero shift, a shift multiple of 8, and so on. Perhaps this will speed up the overall process, but, as practice has shown, such cases are less frequent than in every eighth shift, and each condition and operation adds additional execution time.

And yes, Regent said something about byte order. I did not begin to understand this, because the option that exists now completely suits me. If you get a set of bytes from a number of type long and perform a shift with my function, you will get the same result as if you first perform the same shift for a number, and then get a set of bytes from the result. I get a set of bytes from a number with the BitConverter.GetBytes(theLong) function

At the moment, on my computer, my functions perform 10 million shifts for 700-900 ms with a shift value of 0-7 and time is inversely proportional to the shift value divided by 8. That is, the same number of shifts by 8-15 will be faster than 0- 7, and at 16-23 even faster and so on ...

UPD

The specified execution time is for Debug. In the release, everything works 3-4 times faster.