NOT (0x19)

Bitwise NOT operation (one’s complement) for inverting all bits in 256-bit values

This page is a placeholder. All examples on this page are currently AI-generated and are not correct. This documentation will be completed in the future with accurate, tested examples.

Overview

Opcode: 0x19 Introduced: Frontier (EVM genesis)

NOT performs bitwise NOT (one’s complement) on a 256-bit unsigned integer, inverting every bit (0 becomes 1, 1 becomes 0). This operation is fundamental for bit masking, creating inverted patterns, and logical negation in bitwise contexts.

Primary uses: creating inverse masks, clearing bits (NOT + AND), two’s complement conversion (NOT + 1).

Specification

Stack Input:

a (top)

Stack Output:

~a

Gas Cost: 3 (GasFastestStep)

Truth Table (per bit):

a | ~a
--|----
0 |  1
1 |  0

Behavior

NOT pops one value from the stack, inverts all 256 bits, and pushes the result. The operation is:

• Unary: operates on single operand
• Involutory: ~~a = a (double negation returns original)
• Self-inverse: a XOR (~a) = MAX_UINT256

Result: ~a = MAX_UINT256 - a for unsigned interpretation.

Examples

Basic Inversion

import { not } from '@tevm/voltaire/evm/bitwise';
import { createFrame } from '@tevm/voltaire/evm/Frame';

// Invert bits
const value = 0b11001100n;
const frame = createFrame({ stack: [value] });
const err = not(frame);

// All 256 bits inverted (showing lower byte)
const MAX = (1n << 256n) - 1n;
console.log(frame.stack[0] & 0xFFn);  // 0b00110011

Create Inverse Mask

// Create mask to clear specific bits
const setBits = 0xFFn;  // Lower 8 bits
const frame = createFrame({ stack: [setBits] });
not(frame);

const clearMask = frame.stack[0];
// clearMask = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00
// Use with AND to clear lower 8 bits

Zero to Max

// NOT of zero is MAX_UINT256
const frame = createFrame({ stack: [0n] });
not(frame);

const MAX = (1n << 256n) - 1n;
console.log(frame.stack[0] === MAX);  // true

Max to Zero

// NOT of MAX_UINT256 is zero
const MAX = (1n << 256n) - 1n;
const frame = createFrame({ stack: [MAX] });
not(frame);

console.log(frame.stack[0]);  // 0n

Double Negation (Involution)

// ~~a = a
const value = 0x123456789ABCDEFn;

const frame1 = createFrame({ stack: [value] });
not(frame1);
const inverted = frame1.stack[0];

const frame2 = createFrame({ stack: [inverted] });
not(frame2);

console.log(frame2.stack[0] === value);  // true (restored)

Two’s Complement Preparation

// Two's complement: -a = ~a + 1
const value = 5n;
const frame = createFrame({ stack: [value] });
not(frame);

const onesComplement = frame.stack[0];
const twosComplement = onesComplement + 1n;
// twosComplement represents -5 in two's complement

Gas Cost

Cost: 3 gas (GasFastestStep)

NOT shares the lowest gas tier with:

• AND (0x16), OR (0x17), XOR (0x18)
• BYTE (0x1a)
• SHL (0x1b), SHR (0x1c), SAR (0x1d)
• ADD (0x01), SUB (0x03)
• Comparison operations

Edge Cases

Zero Input

// NOT 0 = MAX_UINT256
const frame = createFrame({ stack: [0n] });
not(frame);

const MAX = (1n << 256n) - 1n;
console.log(frame.stack[0] === MAX);  // true

Maximum Input

// NOT MAX_UINT256 = 0
const MAX = (1n << 256n) - 1n;
const frame = createFrame({ stack: [MAX] });
not(frame);

console.log(frame.stack[0]);  // 0n

Alternating Pattern

// NOT 0xAAAA... = 0x5555...
const pattern = 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAn;
const expected = 0x5555555555555555555555555555555555555555555555555555555555555555n;

const frame = createFrame({ stack: [pattern] });
not(frame);

console.log(frame.stack[0] === expected);  // true

Single Bit Set

// NOT with single bit set (bit 0)
const singleBit = 1n;
const frame = createFrame({ stack: [singleBit] });
not(frame);

// Result: all bits except bit 0 are set
const expected = ((1n << 256n) - 1n) - 1n;
console.log(frame.stack[0] === expected);  // true

Stack Underflow

// Empty stack
const frame = createFrame({ stack: [] });
const err = not(frame);

console.log(err);  // { type: "StackUnderflow" }

Out of Gas

// Insufficient gas
const frame = createFrame({ stack: [0x123n], gasRemaining: 2n });
const err = not(frame);

console.log(err);  // { type: "OutOfGas" }
console.log(frame.gasRemaining);  // 0n

Common Usage

Clear Bits (NOT + AND)

// Clear specific bits from value
function clearBits(uint256 value, uint256 bitsToClear) pure returns (uint256) {
    return value & ~bitsToClear;  // NOT creates inverse mask
}

// Example: Clear lower 160 bits
uint256 value = 0x123456789ABCDEF0123456789ABCDEF012345678;
uint256 mask = (1 << 160) - 1;  // Lower 160 bits
uint256 result = value & ~mask;  // Clear lower bits

Revoke Permissions

// Remove specific permission flags
uint256 constant READ = 1 << 0;
uint256 constant WRITE = 1 << 1;
uint256 constant EXECUTE = 1 << 2;

function revokePermission(uint256 current, uint256 toRevoke) pure returns (uint256) {
    return current & ~toRevoke;
}

// Usage
uint256 perms = READ | WRITE | EXECUTE;  // All permissions
perms = revokePermission(perms, WRITE);   // Remove WRITE (keeps READ, EXECUTE)

Create Bit Mask

// Create mask for all bits except specified range
function createExclusionMask(uint256 start, uint256 len) pure returns (uint256) {
    uint256 inclusionMask = ((1 << len) - 1) << start;
    return ~inclusionMask;  // Invert to get exclusion mask
}

// Example: Mask all bits except bits 8-15
uint256 mask = createExclusionMask(8, 8);
// mask = ~0x0000...00FF00 = 0xFFFF...FF00FF

Two’s Complement Negation

// Negate signed integer (two's complement)
function negate(uint256 value) pure returns (uint256) {
    return ~value + 1;  // Two's complement: -x = ~x + 1
}

// Example
int256 x = 42;
int256 negX = int256(negate(uint256(x)));  // -42

Invert Bitmap

// Invert all flags in bitmap
mapping(uint256 => uint256) public bitmap;

function invertBitmap(uint256 bucket) internal {
    bitmap[bucket] = ~bitmap[bucket];
}

Complement in Range Checks

// Check if value is NOT in set (using bitmap)
function isNotMember(uint256 value, uint256 bitmap) pure returns (bool) {
    uint256 mask = 1 << (value % 256);
    return (bitmap & mask) == 0;
    // Equivalent to: (~bitmap & mask) != 0
}

Implementation

TypeScript

/**
 * NOT opcode (0x19) - Bitwise NOT operation (one's complement)
 */
export function op_not(frame: FrameType): EvmError | null {
  // Consume gas (GasFastestStep = 3)
  frame.gasRemaining -= 3n;
  if (frame.gasRemaining < 0n) {
    frame.gasRemaining = 0n;
    return { type: "OutOfGas" };
  }

  // Pop operand
  if (frame.stack.length < 1) return { type: "StackUnderflow" };
  const a = frame.stack.pop();

  // Compute bitwise NOT (one's complement)
  // Note: In JavaScript, ~a only works for 32-bit integers
  // For 256-bit: use MAX_UINT256 XOR or subtraction
  const MAX_UINT256 = (1n << 256n) - 1n;
  const result = a ^ MAX_UINT256;  // Equivalent to ~a for 256-bit

  // Push result
  if (frame.stack.length >= 1024) return { type: "StackOverflow" };
  frame.stack.push(result);

  // Increment PC
  frame.pc += 1;

  return null;
}

Testing

Test Coverage

import { describe, it, expect } from 'vitest';
import { op_not } from './not.js';

describe('NOT (0x19)', () => {
  it('inverts all bits', () => {
    const value = 0b11001100n;
    const frame = createFrame({ stack: [value] });
    expect(op_not(frame)).toBeNull();

    const MAX = (1n << 256n) - 1n;
    const expected = MAX - value;  // ~a = MAX - a
    expect(frame.stack[0]).toBe(expected);
  });

  it('converts zero to MAX', () => {
    const frame = createFrame({ stack: [0n] });
    expect(op_not(frame)).toBeNull();

    const MAX = (1n << 256n) - 1n;
    expect(frame.stack[0]).toBe(MAX);
  });

  it('converts MAX to zero', () => {
    const MAX = (1n << 256n) - 1n;
    const frame = createFrame({ stack: [MAX] });
    expect(op_not(frame)).toBeNull();
    expect(frame.stack[0]).toBe(0n);
  });

  it('is involutory (~~a = a)', () => {
    const value = 0x123456789ABCDEFn;
    const frame1 = createFrame({ stack: [value] });
    op_not(frame1);

    const frame2 = createFrame({ stack: [frame1.stack[0]] });
    op_not(frame2);

    expect(frame2.stack[0]).toBe(value);
  });

  it('inverts alternating pattern', () => {
    const pattern = 0xAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAn;
    const expected = 0x5555555555555555555555555555555555555555555555555555555555555555n;

    const frame = createFrame({ stack: [pattern] });
    expect(op_not(frame)).toBeNull();
    expect(frame.stack[0]).toBe(expected);
  });

  it('prepares two\'s complement', () => {
    const value = 5n;
    const frame = createFrame({ stack: [value] });
    expect(op_not(frame)).toBeNull();

    const onesComplement = frame.stack[0];
    const twosComplement = (onesComplement + 1n) & ((1n << 256n) - 1n);

    // Two's complement of 5 should be -5 (MAX_UINT256 - 4)
    const MAX = (1n << 256n) - 1n;
    expect(twosComplement).toBe(MAX - 4n);
  });

  it('returns StackUnderflow with empty stack', () => {
    const frame = createFrame({ stack: [] });
    expect(op_not(frame)).toEqual({ type: 'StackUnderflow' });
  });

  it('returns OutOfGas when insufficient gas', () => {
    const frame = createFrame({ stack: [0x123n], gasRemaining: 2n });
    expect(op_not(frame)).toEqual({ type: 'OutOfGas' });
  });
});

Edge Cases Tested

• Basic bit inversion
• Zero to MAX_UINT256
• MAX_UINT256 to zero
• Involutory property (~~a = a)
• Alternating bit patterns
• Two’s complement preparation
• Single bit set
• Stack underflow
• Out of gas

Security

Two’s Complement Confusion

// WRONG: NOT alone doesn't negate signed integers
function negate(int256 x) pure returns (int256) {
    return int256(~uint256(x));  // Missing +1 for two's complement!
}

// CORRECT: Two's complement requires NOT + 1
function negate(int256 x) pure returns (int256) {
    return int256(~uint256(x) + 1);  // -x = ~x + 1
}

Mask Creation Errors

// DANGEROUS: Creating masks without boundary checks
function clearLowerBits(uint256 value, uint256 numBits) pure returns (uint256) {
    require(numBits <= 256, "invalid bit count");
    uint256 mask = (1 << numBits) - 1;
    return value & ~mask;
}

// Risk: numBits > 256 causes mask overflow

Incorrect Bit Clearing

// WRONG: Using NOT alone (clears all OTHER bits)
function clearFlag(uint256 flags, uint256 flag) pure returns (uint256) {
    return ~flag;  // Returns inverted flag, not modified flags!
}

// CORRECT: NOT + AND to clear specific bits
function clearFlag(uint256 flags, uint256 flag) pure returns (uint256) {
    return flags & ~flag;
}

Signed vs Unsigned

// PITFALL: NOT on unsigned vs signed interpretation
uint256 unsigned_val = 5;
int256 signed_val = 5;

// NOT on unsigned: MAX_UINT256 - 5
uint256 unsigned_result = ~unsigned_val;  // Very large positive number

// Two's complement on signed: -6 (not -5!)
int256 signed_result = int256(~uint256(signed_val));  // -6, not -5
int256 proper_negation = -signed_val;  // -5 (correct)

Benchmarks

NOT is one of the fastest EVM operations:

Execution time (relative):

• NOT: 1.0x (baseline, fastest tier)
• AND/OR/XOR: 1.0x (same tier)
• ADD: 1.0x (same tier)
• MUL: 1.2x
• DIV: 2.5x

Gas efficiency:

• 3 gas per 256-bit NOT operation
• ~333,333 NOT operations per million gas
• Native hardware instruction on all platforms

References

• Yellow Paper - Section 9.1 (Bitwise Logic Operations)
• EVM Codes - NOT
• Solidity Docs - Bitwise Operators
• Two’s Complement - Signed integer representation

Related Documentation

• AND (0x16) - Bitwise AND operation
• OR (0x17) - Bitwise OR operation
• XOR (0x18) - Bitwise XOR operation
• SUB (0x03) - Subtraction (for two’s complement)