Bitwise Operations: AND, OR, XOR, Shifts and Bit Masks for Flags

Version note: The code in this post was built and run with .NET 10 (C# 14), TypeScript 7.0 and Node.js 24; the C# examples are tested with xUnit v3 4.0.3.

Guess First

Book IDs at Bookstore have grown; they're now around 2^40. A helper function in the frontend takes the last byte of the ID to decide which cache bucket it lands in: bookId & 0xff. For bookId = 2 ** 40 + 3 the result should be 3. So what does bookId | 0 give? The number itself, zero, or something else?

A question on the C# side too: with int one = 1; int shift = 32;, what is one << shift? Shift a 1 left 32 times in a 32-bit int and the bit falls off, so the result should be 0, right?

The answer to both is "no". In the first post of the series, "Binary and Hexadecimal", we learned to read bits. In this post we'll change them one by one and see the reason for both surprises at the bit level.

Six Operators: AND, OR, XOR, NOT and Shifts

Bitwise operators process the bits at the same position in two numbers independently of each other. There's no carry as in addition; every bit is computed in its own column.

static string Bits(uint value, int width = 8) => Convert.ToString(value, 2).PadLeft(width, '0');

uint a = 0b1100_1010;
uint b = 0b1010_0110;
Console.WriteLine($"a      {Bits(a)}");
Console.WriteLine($"b      {Bits(b)}");
Console.WriteLine($"a & b  {Bits(a & b)}");
Console.WriteLine($"a | b  {Bits(a | b)}");
Console.WriteLine($"a ^ b  {Bits(a ^ b)}");
Console.WriteLine($"~a     {Bits(~a & 0xFF)}");
Console.WriteLine($"~a     {Bits(~a, 32)}");

a      11001010
b      10100110
a & b  10000010
a | b  11101110
a ^ b  01101100
~a     00110101
~a     11111111111111111111111100110101

AND (&) gives 1 only when both bits are 1; you use it to "filter". OR (|) gives 1 when either bit is 1; you use it to "add". XOR (^, exclusive OR) gives 1 when the bits differ; you use it to "flip". NOT (~) inverts every bit. Note the last two lines: a looks like an 8-bit value, but its type is uint, so 32 bits. ~a also turns the upper 24 zeros into ones. If you only want the low byte, you have to mask with & 0xFF. This idea of a "mask" is the basis of the rest of the post.

Shifts: Moving, Multiplying and Dividing

x << n moves the bits n positions to the left, with zeros coming in from the right. Each shift is a multiplication by 2: 5 << 3 = 5 × 8 = 40. Shifting right is dividing by 2: 40 >> 3 = 5. What comes in from the left on a right shift depends on the type of the number:

int negative = -16;
Console.WriteLine(negative >> 2);    // -4
Console.WriteLine(negative >>> 2);   // 1073741820
Console.WriteLine(-7 / 2);            // -3
Console.WriteLine(-7 >> 1);           // -4

-16        11111111111111111111111111110000
-16 >> 2   11111111111111111111111111111100
-16 >>> 2  00111111111111111111111111111100

On a signed type, >> performs an arithmetic shift: it copies the leftmost bit, the sign bit, so a negative number stays negative. >>>, added in C# 11, performs a logical shift, also called unsigned right shift: zeros always come in from the left, whatever the type. Before that, you needed casts like (int)((uint)x >> 2) for the same result. On unsigned types (uint, ulong) the two operators behave the same. Why a negative number's bit pattern looks like this, that is, two's complement, is covered in detail in the next post of the series.

The last two lines show a subtle difference: -7 / 2 rounds toward zero and gives -3, while -7 >> 1 rounds toward negative infinity and gives -4. The rule "shifting right is dividing by 2" doesn't hold exactly for negative numbers. The JIT already turns a division by a constant power of two into code that uses shifts, adding a correction step for negative numbers. You don't need to write >> 1 instead of / 2 for performance; if you do, the result changes for negative numbers.

Managing Flags with Bit Masks: Set, Clear, Toggle, Test

Every user at Bookstore has a set of permissions. Instead of keeping them in separate bool columns, we keep them in the bits of a single number. The general use of enums and the [Flags] attribute was covered in the C# Fundamentals series post "Enums in C#: Underlying Types, [Flags], Parse and switch"; here we go down to the bit level:

namespace Bookstore.Security;

[Flags]
public enum Permission : uint
{
    None = 0,
    ViewCatalog = 1u << 0,
    PlaceOrder = 1u << 1,
    WriteReview = 1u << 2,
    ManageInventory = 1u << 3,
    IssueRefund = 1u << 4,
    ManageUsers = 1u << 5,
    Customer = ViewCatalog | PlaceOrder | WriteReview,
    Staff = Customer | ManageInventory | IssueRefund,
}

public static class PermissionBits
{
    public static Permission Grant(Permission current, Permission add) => current | add;

    public static Permission Revoke(Permission current, Permission remove) => current & ~remove;

    public static Permission Toggle(Permission current, Permission flip) => current ^ flip;

    // All requested bits must be present
    public static bool HasAll(Permission current, Permission required) =>
        required != Permission.None && (current & required) == required;

    // At least one requested bit must be present
    public static bool HasAny(Permission current, Permission wanted) => (current & wanted) != 0;
}

Writing the values as 1u << n shows clearly that each permission gets one bit; it leads to fewer mistakes than writing 1, 2, 4, 8, 16. The four operations are four idioms. Set: current | add. Clear: current & ~remove, meaning "keep everything except the bits you want to remove". Toggle: current ^ flip. Test: (current & required) == required. On Alice's permissions:

Permission alice = Permission.Customer;                              // Customer = 00000111
alice = PermissionBits.Grant(alice, Permission.IssueRefund);         // Customer, IssueRefund = 00010111
alice = PermissionBits.Revoke(alice, Permission.WriteReview);        // ViewCatalog, PlaceOrder, IssueRefund = 00010011
alice = PermissionBits.Toggle(alice, Permission.WriteReview);        // Customer, IssueRefund = 00010111
PermissionBits.HasAll(alice, Permission.PlaceOrder | Permission.IssueRefund);  // True
PermissionBits.HasAll(alice, Permission.PlaceOrder | Permission.ManageUsers);  // False
PermissionBits.HasAny(alice, Permission.PlaceOrder | Permission.ManageUsers);  // True

The None check in HasAll isn't decoration. The framework's HasFlag method returns True for alice.HasFlag(Permission.None), because x & 0 == 0 is always true. If a "required permission" value read from configuration comes back empty, HasFlag lets everyone in.

BitOperations: Counting, Finding, Rounding

System.Numerics.BitOperations contains methods that use the dedicated CPU instructions for this work when the CPU supports them. You don't need to write loops by hand:

uint staff = (uint)Permission.Staff;
Console.WriteLine(BitOperations.PopCount(staff));                                // 5
Console.WriteLine(BitOperations.TrailingZeroCount((uint)Permission.IssueRefund)); // 4
Console.WriteLine(BitOperations.LeadingZeroCount((uint)Permission.IssueRefund));  // 27
Console.WriteLine(BitOperations.Log2((uint)Permission.IssueRefund));              // 4
Console.WriteLine(BitOperations.IsPow2((uint)Permission.IssueRefund));            // True
Console.WriteLine(BitOperations.IsPow2((uint)Permission.Customer));               // False
Console.WriteLine(BitOperations.RoundUpToPowerOf2(1000u));                        // 1024
Console.WriteLine(BitOperations.RoundUpToPowerOf2(1024u));                        // 1024

PopCount (population count) gives the number of set bits: the Staff role has 5 permissions. TrailingZeroCount gives the position of the rightmost 1, LeadingZeroCount the number of zeros on the left; 32 − 27 − 1 = 4, so IssueRefund is bit number 4. IsPow2 checks whether exactly one bit is set; where an API expects "a single permission" and receives a combined value, it catches it. RoundUpToPowerOf2 is used to round a buffer or hash table size up to the next power of two. Since .NET 7 the same methods are also available on the types themselves through generic math: uint.PopCount(staff).

There's a classic idiom for walking the permissions in a flags value one at a time:

uint remaining = (uint)Permission.Staff;
while (remaining != 0)
{
    int index = BitOperations.TrailingZeroCount(remaining);
    Console.Write($"{(Permission)(1u << index)} ");
    remaining &= remaining - 1;   // clear the rightmost 1
}
// ViewCatalog PlaceOrder WriteReview ManageInventory IssueRefund

x - 1 turns the rightmost 1 into 0 and the zeros to its right into 1s; so x & (x - 1) clears just the rightmost 1. The loop runs as many times as there are set bits, not 32 times.

XOR: Useful but Hard to Read

XOR has three properties: x ^ x = 0, x ^ 0 = x, and order doesn't matter. A few well-known tricks come out of them:

int p = 12, q = 7;
p ^= q; q ^= p; p ^= q;
Console.WriteLine($"{p} {q}");                    // 7 12

int[] arr = [3, 9, 3, 4, 9];
int lonely = 0;
foreach (int n in arr) lonely ^= n;
Console.WriteLine(lonely);                         // 4

Console.WriteLine(BitOperations.PopCount(0b1011u) & 1);  // 1 (odd number of set bits)

A swap without a temporary variable, finding the single element left over in an array because pairs cancel each other out, and parity, whether the number of set bits is odd or even. Parity and XOR do real work in error detection, in RAID and in hash functions. But don't write an XOR swap in application code. In modern C#, (p, q) = (q, p) is both readable and avoids this trap: if both variables refer to the same memory location, for example the same array element through ref, an XOR swap zeroes the value. If a code reviewer has to stop and think "what does this do", that code is expensive.

TypeScript: Every Bitwise Operation Is 32 Bits

In JavaScript, number is a 64-bit floating point value. But bitwise operators first convert their operands to a 32-bit signed integer (ToInt32, as the specification calls it), perform the operation, and return the result as a 32-bit integer again. That conversion drops the upper bits without any warning:

console.log(2 ** 31 | 0);               // -2147483648
console.log((2 ** 32 + 5) | 0);         // 5
console.log(0x80000000 | 1);            // -2147483647
console.log((0x80000000 | 1) >>> 0);    // 2147483649
console.log(~~3.7, ~~-3.7, Math.trunc(-3.7));  // 3 -3 -3
console.log(1 << 32, 1 << 31);          // 1 -2147483648

const bookId = 2 ** 40 + 3;
console.log(bookId, bookId & 0xff, bookId | 0);  // 1099511627779 3 3

The answer to the Guess First question: bookId | 0 gives 3. Everything above bit 40 of the ID is gone. & 0xff happened to be right because we only wanted the low 8 bits anyway. Had the same function used | 0 to "truncate the ID to an integer", every ID above 2^31 would break, and you'd never see it with the small IDs in your test data.

The >>> 0 trick makes the result be read as an unsigned 32-bit value; that's why we saw 32 ones with (-1 >>> 0).toString(2) in the first post. ~~x is an old "drop the fraction" trick that relies on the same ToInt32 conversion; it gives wrong results above 2^31, so use Math.trunc.

If you need bitwise operations on values wider than 32 bits, use BigInt. BigInt works at arbitrary width and applies bitwise operators correctly, but it can't be mixed with number:

const big = 2n ** 40n + 3n;
console.log(big & 0xffn, big | 1n << 50n);    // 3n 1126999418470403n
console.log(BigInt.asUintN(64, -1n));          // 18446744073709551615n
console.log(BigInt.asIntN(8, 255n));           // -1n

BigInt.asUintN and asIntN fit a value into a given bit width; you can think of them as the counterpart of unchecked casts in C#. How large IDs break on their way to the frontend through JSON is covered in detail in the next post of the series.

In Production

Storing a flags enum in a single integer column in the database is practical but needs a few rules. Once a bit number has been used, its meaning never changes. Removing ManageUsers and giving its bit to a new permission grants the new permission to everyone whose old rows have that bit set. New permissions always go into an unused bit; the bit of a removed permission stays empty.

Watch the underlying type. SQL Server has no unsigned integer type. When a uint enum uses bit 31, the value is 2147483648; force it into an int column and it's stored as -2147483648. If you expect more than 31 permissions, choose long and bigint from the start.

Think about query cost. WHERE (Permissions & 16) = 16 looks at an expression, not at the column itself, so it can't use an index and scans the table. If "find everyone with the IssueRefund permission" runs often, keeping permissions as rows in a separate table may fit better. A bit mask works well when checking a user's own permissions and gets awkward for reporting.

Send names, not numbers, in the API. System.Text.Json writes enums as numbers by default: {"Name":"alice","Permissions":23}. With JsonStringEnumConverter the flags value becomes readable: {"Name":"alice","Permissions":"Customer, IssueRefund"}, and the same format can be read back. If you send numbers, the frontend has to do bitwise operations and runs into the 32-bit limit above.

Common Pitfalls

Operator precedence. The == operator binds tighter than &; flags & 4 == 4 actually means flags & (4 == 4). C# doesn't compile it:

int flags = 0b0110;
if (flags & 4 == 4)
{
    Console.WriteLine("can write reviews");
}
// error CS0019: Operator '&' cannot be applied to operands of type 'int' and 'bool'

TypeScript catches it too: error TS2363: The right-hand side of an arithmetic operation must be of type 'any', 'number', 'bigint' or an enum type. But in plain JavaScript, 4 == 4 becomes true, then 1, and the code runs silently. With flags = 0b0011 (ViewCatalog and PlaceOrder set, WriteReview not set), the condition flags & 4 == 4 becomes 3 & 1 = 1 and prints "can write reviews". Always put bitwise expressions in parentheses: (flags & 4) === 4.

Shift counts are masked. The answer to the second Guess First question is 1:

int one = 1;
int shift = 32;
Console.WriteLine(one << shift);   // 1
Console.WriteLine(one << 33);      // 2
long oneL = 1;
Console.WriteLine(oneL << 64);     // 1
Console.WriteLine(oneL << 63);     // -9223372036854775808

According to the C# specification, only the low 5 bits of the shift count are used for int and uint, and the low 6 bits for long and ulong. Since 32 & 31 = 0, 1 << 32 doesn't shift at all. The shift instructions of x86 and x64 processors mask the count the same way; C# defines this behavior as a rule of the language. JavaScript has the same rule: 1 << 32 gives 1. If the shift count comes from a variable, for example a bit number read from the database, check its range first.

Values that aren't powers of two in a [Flags] enum. A mistaken value like ManageUsers = 3 behaves like the combination of ViewCatalog and PlaceOrder, and its ToString output is confusing too. Define single permissions with 1u << n and combinations with |, and verify in a test that every single permission is one bit with BitOperations.IsPow2.

Expecting a logical right shift on a signed type. If you take the upper bits of a hash to compute a bucket number with int and >>, negative hashes give you a negative index. Either convert to uint or use >>>.

A Small Experiment

★☆☆ Add Count(Permission p) to PermissionBits and write it without BitOperations.PopCount, using only an x &= x - 1 loop. Write a test that compares the result with PopCount.

★★☆ Write a function that reverses the bits of a byte (0b0000_0001 → 0b1000_0000) using only shifts, AND and OR. Test that reversing twice gives back the value for all 256 values.

★★★ Write a BigInt-based grant, revoke, has trio in TypeScript for 64-bit permission values. Compare it on bit 40 with a version that does the same with number, and show which line breaks.

In this post we changed bits, but we left one question open: why is the bit pattern of -16 11111111111111111111111111110000? The next post in the series, "Integer Representation: Two's Complement, Overflow, Endianness and the Lost long ID in JSON", starts with that question; we'll see why Math.Abs(int.MinValue) throws an exception, why byte order matters in file formats and on the network, and how a large long ID silently changes on its way to the frontend through JSON.