Swift Bitshift Integers in Array to the Right-CodePudding

I've found a similar example in Python.

Essentially, say you have an array which is [1, 2, 3], and in binary that would be [0b00000001, 0b00000010, 0b00000011], what's the fastest way to bitshift that into [0b00000000, 0b10000001, 0b00000001]?

Basically bitshifting an array as if it were one huge int. (The left-hand side can always be assumed to be 0.)

Unfortunately I haven't got any code, because I have no clue how to achieve this, sorry!

CodePudding user response：

(I do not know Swift!)

var bignum = [1, 2, 3]
var carry = 0
let signBit = 1 << 31 // or 1 << 63 or int.min
for i in 00..<bignum.count {
    var n = bignum[i]
    let nextCarry = (n & 1) == 1 ? signBit : 0
    n = (n >> 1) & ~signBit
    if carry {
        n = n | carry
    }
    bignum[i] = n
    carry = nextCarry;
}

The sign bit must be set when the prior number was odd (ended with bit 1).

A shift-right (logical shift right, >>> in java) must be undone from a persisting sign, as >> is an arithmetical shift right, conserving the sign.

The sign bit is the highest bit, but I believe Swift has both 32 and 64 bit ints. There might be some constant, like java's Integer.MIN_VALUE (int.min?). One could also use a signed int and shift the signBit to the right until it becomes negative.

In general UInt64 would be best to use (>> then shifting in a bit 0).

CodePudding user response：

I think you could do it something like this:

func bitShift(array: [UInt8]) -> [UInt8] {
  var output = array

  var prevParity = false

  for i in 0..<output.count {
    // check parity of current value and store it
    let tempParity = (output[i] & 1) == 1

    // bitshift the current value to the right
    output[i] = output[i] >> 1

    if prevParity {
      // add on the first one if the previous value was odd
      output[i] = output[i] | 0b10000000
    }

    // store tempParity into prevParity for next loop
    prevParity = tempParity
  }

  return output
}

Advanced operators... https://docs.swift.org/swift-book/LanguageGuide/AdvancedOperators.html