CodeStepByStep

This site requires JavaScript. It looks like you have disabled JavaScript in your browser or are using a browser that does not support JavaScript. Please enable it or try another browser.

< bit_array_puzzle

bitmask1 >

Main Page → Exercises → C → Solve an Exercise

bitmask0

Language/Type: C bitwise operators bit manipulation

Author: Julie Zelenski (on 2018/02/03)

A bit vector is an unsigned value treated as a set of independent boolean values. The bit at a given position represents a particular member and if that bit is on in the bit vector, the set contains that member. Changing a particular bit allows you to add or remove a member from the set. When operating on a bit vector, you apply a bitwise operator with a mask to isolate the bits of interest.

Do you know how to perform operations on a bit vector? Test yourself with the expressions below. Assume mine and yours are unsigned ints. The terms "low" and "high" refer to "less significant" and "more significant", i.e. the lowest bit is the least significant. (You will also see "rightmost" and "leftmost" used as synonyms for most and least significant.)

test if mine has lowest bit on
`yours = yours \| 1` `(yours & mine) == yours` `yours = yours & ~1` `yours = yours ^ 1` `(mine & 1) != 0` `mine = mine & yours` `mine = mine & ~yours` `mine = mine \| yours` (order shuffled)
set lowest bit in yours
`(mine & 1) != 0` `yours = yours & ~1` `mine = mine \| yours` `yours = yours \| 1` `(yours & mine) == yours` `yours = yours ^ 1` `mine = mine & ~yours` `mine = mine & yours` (order shuffled)
clear lowest bit in yours
`yours = yours \| 1` `mine = mine \| yours` `yours = yours ^ 1` `(yours & mine) == yours` `(mine & 1) != 0` `mine = mine & ~yours` `yours = yours & ~1` `mine = mine & yours` (order shuffled)
toggle lowest bit in yours
`(yours & mine) == yours` `mine = mine & yours` `yours = yours & ~1` `mine = mine & ~yours` `yours = yours \| 1` `(mine & 1) != 0` `yours = yours ^ 1` `mine = mine \| yours` (order shuffled)
union mine with yours
`(yours & mine) == yours` `yours = yours \| 1` `(mine & 1) != 0` `mine = mine & ~yours` `mine = mine & yours` `yours = yours ^ 1` `yours = yours & ~1` `mine = mine \| yours` (order shuffled)
intersect mine with yours
`yours = yours \| 1` `(mine & 1) != 0` `yours = yours ^ 1` `mine = mine \| yours` `mine = mine & yours` `mine = mine & ~yours` `yours = yours & ~1` `(yours & mine) == yours` (order shuffled)
remove yours from mine
`mine = mine \| yours` `mine = mine & ~yours` `yours = yours & ~1` `yours = yours ^ 1` `mine = mine & yours` `yours = yours \| 1` `(mine & 1) != 0` `(yours & mine) == yours` (order shuffled)
is yours a subset of mine?
`yours = yours & ~1` `yours = yours ^ 1` `mine = mine & ~yours` `(yours & mine) == yours` `yours = yours \| 1` `mine = mine \| yours` `mine = mine & yours` `(mine & 1) != 0` (order shuffled)

Ad Blocker Detected

Main Page → Exercises → C → Solve an Exercise

bitmask0