Could I add a one hot encoding to each feature representing "has data" versus "has no data"
If you are using Python, the Imputer class could be a way to fill in the holes. You can use it to define what counts as a missing value and define a method for replacing those (mean, median, mode, constant value). Without knowing what the data is, it's hard to say whether this is an ideal solution, but it is a very quick one.

The Imputer class also includes a MissingIndicator method which would ouput a Boolean array based on the data. This could be another option, and then you could stack the Boolean array onto the original data.