A bitwise bidirectionally rewritable nonvolatile semiconductor storage device capable of performing a high-speed data rewrite, while enhancing endurance characteristics and data-retention characteristics of a memory cell. To achieve high-speed generation of rewrite-bit information indicating that a data rewrite is needed or not, the structure employs a logic circuit corresponding to the number of change patterns of write conditions and concurrently compares between read-out data RO of memory at the start of the data rewrite and prepared write data DIN. After an electrical data rewrite of the memory, the data rewrite is verified based on the rewrite-bit information stored in an internal buffer circuit. This protects an already-rewritten memory cell from unnecessary additional rewrite.