LogoLogo
  • Welcome!
  • Mission Statement
  • Contributing Guidelines
    • Embed CADs in Wiki Articles
  • VEX Worlds Livestream Archive
    • VEX U
    • V5RC High School
    • V5RC Middle School
    • VIQRC Middle School
    • VIQRC Elementary School
    • JROTC
  • ⚙️Hardware
    • Design Fundamentals
      • Gear Ratios
      • Internal Forces (Stress)
      • Torque
      • RPM
      • Center of Mass
    • Introduction to VEX Parts
      • Structure
        • C-Channels and Angles
        • Fasteners
        • Retainers
        • Gussets and Brackets
        • Bearings
        • Plate Metal and Flat Bars
      • Motion
        • High Strength Components
        • Gears and Sprockets
        • Traction Wheels
        • Mecanum Wheels
        • Omnidirectional Wheels
        • Flex Wheels
    • Robot Decorations
      • Part Dyeing
      • Metal Coloring
      • License Plate Holders
    • Lifts
      • Double Reverse Four Bar (DR4B or RD4B)
      • Four Bar
      • Scissor Lift
      • Six Bar
      • Other Lifts
      • Best Practices
    • Shooting Mechanisms
      • Catapult
      • Flywheel
      • Linear Puncher
    • Drivetrains
      • Tank Drive
      • Mecanum Drive
      • Holonomic Drive
      • Designing a Drivetrain
      • Best Practices
    • Pivots & Joints
    • Pneumatics
      • Best Practices - Pneumatics
    • Intakes
    • Flip Out Mechanisms
    • Defensive Mechanisms
    • Misc. Building Techniques
    • VexU
      • Common Manufacturing Techniques
        • 3D Printing
        • Laser Cutting
      • Custom Manufactured Parts Library
      • Commercial Off The Shelf Parts Library
  • 👑Team Administration
    • New Team Resources
      • Creating The Team
      • Gaining Interest for Robotics Teams
      • Attending Competitions
        • Elimination Bracket
    • Team Dynamics
      • Organization Structure and Longevity
      • Member Allocation and Management
      • How *Not* To Run a Team
    • Team Finances
      • One-Year Team Financial Breakdown
      • Funding Your Teams
    • Hosting Competitions
      • Live Streaming
      • Tournament Manager
        • Competition Electronics
        • Creating a Tournament
        • Tools
          • Field Set Control
          • Connecting Mobile Devices
          • Connecting Raspberry Pis
        • Match Control
          • Inputting Match Scores
          • Inputting Skills Scores
          • Inputting Scores on TM Mobile
        • Displays
        • Alliance Selection
      • Additional Event Partner Resources
    • VexU Organization Management
      • Getting Started in VexU
      • Team / Personnel Management
      • Volunteering At Local Events
  • 📚The Judging Process
    • The Engineering Design Process
      • Test and Refine
    • The Engineering Notebook
      • Segments of the Notebook
      • BLRS2 '23-'24 Engineering Notebook
      • Integrating Inventor Models into Documentation
      • Engineering Notebook Rubric Breakdown
    • The Interview
      • Interview Rubric Breakdown
    • Using Notion for an Engineering Notebook
      • How to Setup a Notebook
      • How to Create Entries
      • How to Export a Notebook
      • Purdue SIGBots Notion Template
        • Game Analysis
        • Identify The Problem
        • Brainstorm Solution
        • Select Best Approach & Plan
        • Build Log
        • Programming Log
        • Testing Solution
        • Tournament Recap
        • Innovative Feature
  • 🖥️VEX CAD
    • CAD Programs
      • Inventor
      • Fusion 360
      • Solidworks
      • OnShape
      • Protobot
    • Making a Chassis
      • Inventor Chassis: The Basics
        • Installation
        • User Interface Overview
        • Dark Mode
        • Assemblies
        • Placing Parts
        • Navigating CAD
        • Changing Visual Style
        • Grounding
        • Connecting Two C-Channels
        • Modifying Existing Constraints
        • Toggling Visibility on Existing Parts
        • Completing Half of the Chassis
          • Inner Drive Channel
          • Bearing Flats
          • Motors
          • Wheels
          • Sprockets
          • Spacers, Washers and Standoffs
          • Spacers Cont.
        • Creating Mid-Plane
        • Mirroring
      • Inventor Chassis: Best Practices
        • File Structure
        • Subassemblies
        • Wheel Subassembly
        • Origin Planes
        • Cross Brace
        • Drive Channels
        • Simple Motor iMates
        • Replacing Simple Electronics
        • Completing Half of the Drive
          • Bearing Flats (Best Practice)
          • Wheels
          • Powered Gear
          • Spacer Boxing
          • Spacers, Washers and Standoffs (Best Practice)
        • Model Browser Folders
        • Mirroring (Best Practice)
        • Model Browser Folder (Right)
        • Main Assembly
      • Fusion 360 Chassis
      • Solidworks Chassis, Chain, and Custom Plastic
    • Remembering The Best
      • 62A Skyrise
      • 400X Nothing But Net
      • 2587Z Nothing But Net
      • 365X Starstruck
      • 62A In The Zone
      • 202Z In The Zone
      • 5225A In The Zone
      • 169A Turning Point
      • 929U Turning Point
      • 7K Tower Takeover
      • 5225A Tower Takeover
      • 62A Change Up
    • Scuff Controller
  • 💻Software
    • Odometry
    • Path Planning
    • Robotics Basics
      • Arcade Drive
      • Tank Drive
      • Joystick Deadzones
      • Curvature (Cheesy) Drive
      • Subsystem Toggling
    • Organizing Code
      • Code Style
      • Code Styling Guide
      • Writing Good Comments
      • Version Control
    • Control Algorithms
      • Bang Bang
      • PID Controller
      • Basic Pure Pursuit
      • Flywheel Velocity Control
      • Kalman Filter
      • Take Back Half (TBH) Controller
      • RAMSETE Controller
    • Competition Specific
      • Operator Control
      • Autonomous Control
    • C++ Basics for VEX Robotics
      • Basic Control Flow
      • Enumerations
      • Namespaces (::)
      • Multiple Files (C/C++)
    • VEX Programming Software
      • PROS
        • OkapiLib
      • vexide
      • Robot Mesh Studio (RMS)
      • EasyC
      • RobotC
      • VEXcode
      • Midnight C
    • General
      • Stall Detection
      • Register Programming
      • Sensors and Odometry in Autonomous
      • Embedded Programming Tips
      • Debugging
      • Bit Shift
      • Bit Mask
      • Autoformatting
      • Finite State Machine
      • Data Logging
    • Object Recognition
      • Red Green Buoy
      • AMS
      • OpenCV
      • OpenNI
    • 🤖AI in VRC: Pac-Man Pete
  • ⚡VEX Electronics
    • V5 ESD Protection Board
    • VEX Electronics
      • VEX V5 Brain
        • V5 Electronics Observations and Issues
      • VEX Controller
      • VEXnet and V5 Robot Radio
      • VEX Battery
      • VEX Motors
    • VEX Sensors
      • 3-Pin / ADI Sensors
        • Encoder
        • Potentiometer
        • Limit Switch
        • Bumper Switch
        • Accelerometer
        • Gyroscope
        • Ultrasonic
        • Line Tracker
        • LED Indicator
      • Smart Port Sensors
        • GPS Sensor
        • Rotation Sensor
        • Vision Sensor
        • Optical Sensor
        • Distance Sensor
        • Inertial Sensor (IMU)
        • 3-Wire Expander
    • V5 Brain Wiring Guide
    • Legacy
      • VEX Cortex
      • Power Expander
      • VEX Motor Controller
      • VEX Cortex Wiring Guide
  • General Electronics
    • General Topics
      • External Boards
        • ASUS Tinker Board S
        • Arduino
        • Beagleboard
        • Leaflabs Maple
        • LattePanda
        • Meadow F7 Micro
        • Netduino
        • ODROID-XU4
        • Pandaboard
        • Raspberry Pi
      • Analog-Digital Converter (ADC)
      • Bit-Bang
      • GPIO
      • I2C
      • Jitter
      • Line Noise
      • List of Tools
      • Output Drive
      • Power Consumption
      • Radius Array
      • Resettable Fuse (PTC)
      • SPI
      • Slew Rate
      • Stalling
      • USART
      • UART
      • 5 Volt Tolerant
      • DC Motor Basics
Powered by GitBook
LogoLogo

This work is licensed under a Attribution-ShareAlike 2.0 Generic License

On this page
  • Bit shift
  • Principles
  • Rotations
  • Uses

Was this helpful?

Edit on GitHub
Export as PDF
  1. Software
  2. General

Bit Shift

A bit shift is an operation which moves the bits in the binary representation of a number a specified number of locations left or right.

PreviousDebuggingNextBit Mask

Last updated 4 years ago

Was this helpful?

Bit shift

Along with its cousin, the bit rotate, bit shifts can be used to perform varied yet extremely fast operations on integers with the aid of .

Principles

Humans typically represent integers in base ten notation, but computers use a simpler system where only two states for each digit ("bit") are available - asserted (1) or negated (0). This requires a larger number of place values than a base ten number; typical fixed-width binary numbers range from 8 to 64 bits wide.

A bit shift operates by going through each bit in a binary number and moving that bit a specified number of places to the left or right (more or less significant). While this may seem slow, most processors shift all bits in hardware simultaneously, resulting in a much less complex operation than even a "simple" binary addition. Bit shifts cause some bits to be lost and new bits to be generated; the rules for replacing these bits vary depending on the operation desired:

Shift left

When bits are shifted to the left, negated (zero) bits are always shifted in on the right to replace the shifted bits, and bits shifted to the left are removed and stored in another location. This remains the same regardless of whether the number being shifted is signed or unsigned.

Shifting a signed number left can change the sign of the number if a one is shifted into the sign position (a form of overflow). Beware of this possibility when considering signed (arithmetic) left shifts!

Logical shift right

For unsigned binary numbers, the magnitude of the number is always reduced when shifting to the right, just as it would be when dividing by a power of two. The bits shifted into the left side are therefore always zero in the case of a logical shift right. Performing a right shift on an unsigned variable in C will generate a logical shift.

Arithmetic shift right

Signed binary numbers are typically represented using two's complement notation, where negative numbers have each bit position inverted. The leftmost bit is therefore called the "sign bit", as it is zero for positive numbers and one for negative numbers. Performing a naive fill with zeros would cause a negative two's complement number to become positive, violating the expected result of the number's overall magnitude to be reduced but the sign preserved.

An arithmetic right shift will therefore fill the vacated bits with a copy of the most significant bit, preserving the number's sign. This process is known as sign extension. As a result, shifting the value -1 right by any number of locations (11111111 if represented in a signed byte-wide value) will not change the value, contrary to what one might expect since shifting 1 right will produce zero. C compilers will produce arithmetic right shifts when shifting a signed integer type.

Sign extensions can also be produced, possibly unintentionally, by casting a signed integer type to a larger representation. Casting a char to an int will cause a sign extension, which is expected as the sign of the number should remain the same. But casting a char to an unsigned int will also cause an unintentional sign extension, possibly filling the upper bits with ones or zeroes. Sign extensions of this type can corrupt data if smaller chunks of data are aggregated using shift and mask to construct a wide type. Since the sign extension only occurs if the source type is signed, avoid this error by casting twice, once to a narrow unsigned type and again to the wide type:

unsigned int x = (unsigned int)(unsigned char)y;

Large bit shifts

Rotations

Bit rotates are less common than bit shifts; instead of losing shifted bits and replacing them with a particular fill value, bit rotations take bits off of one side of a binary number and put them back on the other. This does not correspond to any particular familiar arithmetic operation, and is mostly used in cryptography and hashing algorithms.

Uses

  • Multiplication and division - Bit shifts have the same effect as multiplying or dividing by a power of two, but are usually much, much faster. Instead of dividing by 8, shift right by three.

  • Exponentiation with a base of 2 - Left shifts by n bits on the constant 1 will produce the value 2^n. When using this feature, beware of arithmetic overflow.

  • Bit mask checking - To check to see if a particular bit in a binary number is set, shift it right by that many positions and mask by 0x01. While it is faster to mask the original value by a pre-shifted bit mask, this method works for variable arguments and generates a canonical (0/1) boolean value which is more useful in future instructions.

  • Wide type generation - Multi-byte wide types can be generated from their byte components by shifting each byte a specified number of locations (a multiple of eight) to make them fit into the destination number at the correct place.

  • Bit/byte decomposition - Shifting a multi-byte type left or right is often used to break it down into byte or bit-sized components (in combination with an appropriate mask).

Teams Contributed to this Article:

Some processors, such as the HCS12 and AVR () architectures, only support shifting one position at a time. Compilers may generate large numbers of bit-shift instructions, or even a loop, to shift by large or variable quantities, which can slow down execution. However, on some other processors such as ARM (,, , ...) architectures, bit shifting is actually free and costs zero clock cycles in almost all cases, further increasing the value of smart shifting. Modern optimizing compilers will often optimize constant unsigned multiplications or divisions by powers of two into bit shifts.

Shifting by multiples of eight can be even more efficient, as compilers will instead copy the shifted value using a byte offset corresponding to the number of locations shifted, then the invalid locations with the desired fill value.

Bit mask generation - Given a bit position n, one can generate a positive bit mask by performing (1 << n) or a negative mask by performing ~(1 << n). This is very useful when manipulating or pins.

(Purdue SIGBots)

💻
bit masks
Arduino
Raspberry Pi
VEX V5
Pandaboard
mask
registers
GPIO
BLRS