{"history":[],"article":{"id":"1fe5b0d2-fea9-4908-b1aa-8e11ac3f8a55","title":"Barrel shifter","slug":"barrel-shifter","content":":::summary\n:::\n\n# \nA **barrel [shift](https://bliptext.com/articles/bit-shift)er** is a [digital circuit](https://bliptext.com/articles/digital-circuit) that can [shift](https://bliptext.com/articles/bit-shift) a [data word](https://bliptext.com/articles/word-data-type) by a specified number of [bits](https://bliptext.com/articles/bit) without the use of any [sequential logic](https://bliptext.com/articles/sequential-logic), only pure [combinational logic](https://bliptext.com/articles/combinational-logic), i.e. it inherently provides a [binary operation](https://bliptext.com/articles/binary-operation).\nIt can however in theory also be used to implement [unary operations](https://bliptext.com/articles/unary-operation), such as [logical shift left](https://bliptext.com/articles/logical-shift-left), in cases where limited by a fixed amount (e.g. for [address generation unit](https://bliptext.com/articles/address-generation-unit)).\nOne way to implement a barrel shifter is as a sequence of [multiplexers](https://bliptext.com/articles/multiplexer) where the output of one multiplexer is connected to the input of the next multiplexer in a way that depends on the shift distance.\nA barrel shifter is often used to shift and rotate n-bits in modern microprocessors, typically within a single [clock cycle](https://bliptext.com/articles/clock-cycle).\nFor example, take a four-bit barrel shifter, with inputs A, B, C and D. The shifter can cycle the order of the bits ABCD as DABC, CDAB, or BCDA; in this case, no bits are lost.\nThat is, it can shift all of the outputs up to three positions to the right (and thus make any cyclic combination of A, B, C and D).\nThe barrel shifter has a variety of applications, including being a useful component in [microprocessors](https://bliptext.com/articles/microprocessor) (alongside the [ALU](https://bliptext.com/articles/arithmetic-logic-unit)).\n# [Schematic of a 4-bit crossbar barrel shifter. 'x' denotes input bits and y denotes output bits. | upload.wikimedia.org/wikipedia/commons/3/3f/crossbar///barrel///shifter.svg]\n\n# Implementation\nThe very fastest shifters are implemented as full crossbars, in a manner similar to the 4-bit shifter depicted above, only larger.\nThese incur the least delay, with the output always a single gate delay behind the input to be shifted (after allowing the small time needed for the shift count decoder to settle; this penalty, however, is only incurred when the shift count changes).\nThese crossbar shifters require however n2 gates for n-bit shifts.\nBecause of this, the barrel shifter is often implemented as a cascade of parallel 2×1 multiplexers instead, which allows a large reduction in gate count, now growing only with n x log n; the propagation delay is however larger, growing with log n (instead of being constant as with the crossbar shifter).\nFor an 8-bit barrel shifter, two intermediate signals are used which shifts by four and two bits, or passes the same data, based on the value of S[2] and S[1].\nThis signal is then shifted by another multiplexer, which is controlled by S[0]:\nint1 = IN , if S[2] == 0\n= IN << 4, if S[2] == 1\nint2 = int1 , if S[1] == 0\n= int1 << 2, if S[1] == 1\nOUT = int2 , if S[0] == 0\n= int2 << 1, if S[0] == 1\nLarger barrel shifters have additional stages.\nThe cascaded shifter has the further advantage over the full crossbar shifter of not requiring any decoding logic for the shift count.\n\n# Cost\nThe number of multiplexers required for an n-bit word is n\\log_2 n. Five common [word sizes](https://bliptext.com/articles/word-size) and the number of multiplexers needed are listed below:\nCost of critical path in [FO4](https://bliptext.com/articles/fo4) (estimated, without wire delay):\n\n# Uses\nA common usage of a barrel shifter is in the hardware implementation of [floating-point arithmetic](https://bliptext.com/articles/floating-point-arithmetic).\nFor a floating-point add or subtract operation, the [significands](https://bliptext.com/articles/significand) of the two numbers must be aligned, which requires shifting the smaller number to the right, increasing its [exponent](https://bliptext.com/articles/exponent), until it matches the [exponent](https://bliptext.com/articles/exponent) of the larger number.\nThis is done by subtracting the exponents and using the barrel shifter to shift the smaller number to the right by the difference, in one cycle.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T19:08:21.780Z","updated_at":"2025-01-25T19:08:21.780Z","search_vector":"'barrel':1 'shifter':2","search_content":" \n \n\n# \nA **barrel [shift](https://bliptext.com/articles/bit-shift)er** is a [digital circuit](https://bliptext.com/articles/digital-circuit) that can [shift](https://bliptext.com/articles/bit-shift) a [data word](https://bliptext.com/articles/word-data-type) by a specified number of [bits](https://bliptext.com/articles/bit) without the use of any [sequential logic](https://bliptext.com/articles/sequential-logic), only pure [combinational logic](https://bliptext.com/articles/combinational-logic), i.e. it inherently provides a [binary operation](https://bliptext.com/articles/binary-operation).\nIt can however in theory also be used to implement [unary operations](https://bliptext.com/articles/unary-operation), such as [logical shift left](https://bliptext.com/articles/logical-shift-left), in cases where limited by a fixed amount (e.g. for [address generation unit](https://bliptext.com/articles/address-generation-unit)).\nOne way to implement a barrel shifter is as a sequence of [multiplexers](https://bliptext.com/articles/multiplexer) where the output of one multiplexer is connected to the input of the next multiplexer in a way that depends on the shift distance.\nA barrel shifter is often used to shift and rotate n-bits in modern microprocessors, typically within a single [clock cycle](https://bliptext.com/articles/clock-cycle).\nFor example, take a four-bit barrel shifter, with inputs A, B, C and D. The shifter can cycle the order of the bits ABCD as DABC, CDAB, or BCDA; in this case, no bits are lost.\nThat is, it can shift all of the outputs up to three positions to the right (and thus make any cyclic combination of A, B, C and D).\nThe barrel shifter has a variety of applications, including being a useful component in [microprocessors](https://bliptext.com/articles/microprocessor) (alongside the [ALU](https://bliptext.com/articles/arithmetic-logic-unit)).\n# [Schematic of a 4-bit crossbar barrel shifter. 'x' denotes input bits and y denotes output bits. | upload.wikimedia.org/wikipedia/commons/3/3f/crossbar///barrel///shifter.svg]\n\n# Implementation\nThe very fastest shifters are implemented as full crossbars, in a manner similar to the 4-bit shifter depicted above, only larger.\nThese incur the least delay, with the output always a single gate delay behind the input to be shifted (after allowing the small time needed for the shift count decoder to settle; this penalty, however, is only incurred when the shift count changes).\nThese crossbar shifters require however n2 gates for n-bit shifts.\nBecause of this, the barrel shifter is often implemented as a cascade of parallel 2×1 multiplexers instead, which allows a large reduction in gate count, now growing only with n x log n; the propagation delay is however larger, growing with log n (instead of being constant as with the crossbar shifter).\nFor an 8-bit barrel shifter, two intermediate signals are used which shifts by four and two bits, or passes the same data, based on the value of S[2] and S[1].\nThis signal is then shifted by another multiplexer, which is controlled by S[0]:\nint1 = IN , if S[2] == 0\n= IN << 4, if S[2] == 1\nint2 = int1 , if S[1] == 0\n= int1 << 2, if S[1] == 1\nOUT = int2 , if S[0] == 0\n= int2 << 1, if S[0] == 1\nLarger barrel shifters have additional stages.\nThe cascaded shifter has the further advantage over the full crossbar shifter of not requiring any decoding logic for the shift count.\n\n# Cost\nThe number of multiplexers required for an n-bit word is n\\log_2 n. Five common [word sizes](https://bliptext.com/articles/word-size) and the number of multiplexers needed are listed below:\nCost of critical path in [FO4](https://bliptext.com/articles/fo4) (estimated, without wire delay):\n\n# Uses\nA common usage of a barrel shifter is in the hardware implementation of [floating-point arithmetic](https://bliptext.com/articles/floating-point-arithmetic).\nFor a floating-point add or subtract operation, the [significands](https://bliptext.com/articles/significand) of the two numbers must be aligned, which requires shifting the smaller number to the right, increasing its [exponent](https://bliptext.com/articles/exponent), until it matches the [exponent](https://bliptext.com/articles/exponent) of the larger number.\nThis is done by subtracting the exponents and using the barrel shifter to shift the smaller number to the right by the difference, in one cycle.","revisionCount":0},"hasMore":false,"nextCursor":null}

History