Most efficient way to add a serial column to a huge table

Question

What's the fastest way to add a BIGSERIAL column to a huge table (~3 Bil. rows, ~ 174Gb)?

EDIT:

• I want the column to be incremented values for existing rows (NOT NULL).
• I didn't set a fillfactor (which looks like a bad decision in retrospect).
• I don't have a problem with disk space, just want it to be as fast as possible.