Extend left shifts operator to handle non-constant shifts

[kevaundray]

Problem

When the following code is written: lhs << rhs.

In Noir, we convert the code to the following lhs * 2^{rhs}. At the moment, we only allow the rhs to be a constant so that we can compute 2^rhs in the compiler, however it is possible to make this non-constant by doing a sqaure-and-multiply algorithm.

Ideally this algorithm is implemented in the Noir source code and then used in the compiler somehow, but having a builtin initially is also fine. The reason for wanting it to be in the Noir source code is mainly because it involves conditionals and we would be eating our own dog food.

Happy Case

.

Alternatives Considered

No response

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response

[kevaundray]

This is related to #1265

[kevaundray]

Important: Completion of this task involves copying over the bit shift runtime end to end test bit_shifts_runtime

[guipublic]

where can I find the bit_shifts_runtime?

[TomAFrench]

Looks like it was removed in https://github.com/noir-lang/noir/pull/2044/files#diff-5f9d36a0db26fcae53924b92ae5b7e0b4fc595b0764dad759d689264d1584877 without being moved to the new ssa test suite.

[guipublic]

Closing the issue as fixed by #2072